# Solving the recurrence relation $p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$ where $p(1,m) = m$

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

-
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

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.

-
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

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))= ?

...

-