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