Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

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|cite|improve this answer

Your Answer


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.