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
    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.]2012-12-29
  • 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
    Wow! But do you reason forward from the recurrence relation to come up with this?2012-12-31
  • 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))= ?

...