1
$\begingroup$

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

  • 0
    Question updated2012-12-29

2 Answers 2

1

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.

  • 0
    I just computed the numbers until I found a pattern.2012-12-31
0

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

...