Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to solve the following recurrence relation

$$p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$$

$$p(1,m) = m$$ $$p(0,0)=0$$

Any hints or ideas?

(Not a homework assignment)

Edit: n $\le$ m

share|improve this question
    
With the restriction that $latex n\leq m$ (which was added to make the summation sign make sense), the condition that $latex p(n,0) = 0$ is simply $latex p(0,0)=0$, which should be how it would be stated. Please check the question. [Previous 'answer' deleted.] –  Calvin Lin Dec 29 '12 at 8:17
    
Question updated –  anuj919 Dec 29 '12 at 8:55
add comment

2 Answers 2

up vote 1 down vote accepted

With the restriction $1 \leq n \leq m$, we have:

Theorem: $p(n,m)=m!/(m-n)!.$

Proof: We induct on $n$. Base case: It's true for $n=1$, by definition.

Inductive step: Now assume it's true for $n-1$, where $n \geq 2$. Then

\begin{align*} p(n,m) &= n \sum_{k=n-1}^{m-1} p(n-1,k) & \text{by definition} \\ &= n \sum_{k=n-1}^{m-1} \frac{k!}{(k-(n-1))!} & \text{by the inductive hypothesis} \\ &= n \sum_{k=n-1}^{m-1} \binom{k}{n-1}(n-1)! \\ &= n! \sum_{k=n-1}^{m-1} \binom{k}{n-1} \\ &= n! \binom{m}{n} & \text{using some binomial identity} \\ &= \frac{m!}{(m-n)!}. \end{align*}


The binomial identity used is $$\sum_{j=k}^n \binom{j}{k} = \binom{n+1}{k+1};$$ which is listed on Wikipedia.

share|improve this answer
    
Wow! But do you reason forward from the recurrence relation to come up with this? –  anuj919 Dec 31 '12 at 12:37
    
I just computed the numbers until I found a pattern. –  Douglas S. Stones Dec 31 '12 at 15:56
add comment

Try this:

p(1,m) = m

p(2,m) = 2 (p(1,1)+p(1,2)+...+p(1,m-1)) = 2(1+2+3+...+m-1) = 2m(m-1)/2

p(3,m) = 3 (p(2,2)+p(2,3)+...+p(2,m-1)) = 3(2$\cdot$1+3$\cdot$2+...+m(m-1))= ?

...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.