Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Considering the following formulae:

(i) $1+2+3+..+n = n(n+1)/2$

(ii) $1\cdot2+2\cdot3+3\cdot4+...+n(n+1) = n(n+1)(n+2)/3$

(iii) $1\cdot2\cdot3+2\cdot3\cdot4+...+n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4$

Find and prove a 'closed formula' for the sum

$1\cdot2\cdot3\cdot...\cdot k + 2\cdot3\cdot4\cdot...\cdot(k+1) + ... + n(n+1)(n+2)\cdot...\cdot (k+n-1)$

generalizing the formulae above.

I have attempted to 'put' the first 3 formulae together but i am getting know where and wondered where to even start to finding a closed formula.

share|improve this question
    
Do you know how to prove by induction? –  Clive Newstead Oct 23 '12 at 22:27
    
Yes, using the basic step n=1 and then induction step n+1 showing it follows. But don't i need to 'find' the formula before proving it using induction? –  Matt Oct 23 '12 at 22:29

4 Answers 4

up vote 6 down vote accepted

The pattern looks pretty clear: you have

$$\begin{align*} &\sum_{i=1}^ni=\frac12n(n+1)\\ &\sum_{i=1}^ni(i+1)=\frac13n(n+1)(n+2)\\ &\sum_{i=1}^ni(i+1)(i+2)=\frac14n(n+1)(n+2)(n+3)\;, \end{align*}\tag{1}$$

where the righthand sides are closed formulas for the lefthand sides. Now you want

$$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)\;;$$

what’s the obvious extension of the pattern of $(1)$? Once you write it down, the proof will be by induction on $n$.

Added: The general result, of which the three in $(1)$ are special cases, is $$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)=\frac1{k+1}n(n+1)(n+2)\dots(n+k)\;.\tag{2}$$ For $n=1$ this is $$k!=\frac1{k+1}(k+1)!\;,$$ which is certainly true. Now suppose that $(2)$ holds. Then

$$\begin{align*}\sum_{i=1}^{n+1}i(i+1)&(i+2)\dots(i+k-1)\\ &\overset{(1)}=(n+1)(n+2)\dots(n+k)+\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)\\ &\overset{(2)}=(n+1)(n+2)\dots(n+k)+\frac1{k+1}n(n+1)(n+2)\dots(n+k)\\ &\overset{(3)}=\left(1+\frac{n}{k+1}\right)(n+1)(n+2)\dots(n+k)\\ &=\frac{n+k+1}{k+1}(n+1)(n+2)\dots(n+k)\\ &=\frac1{k+1}(n+1)(n+2)\dots(n+k)(n+k+1)\;, \end{align*}$$

exactly what we wanted, giving us the induction step. Here $(1)$ is just separating the last term of the summation from the first $n$, $(2)$ is applying the induction hypothesis, $(3)$ is pulling out the common factor of $(n+1)(n+2)\dots(n+k)$, and the rest is just algebra.

share|improve this answer
    
For each extra bracket (n+1) then (n+2) you're adding +1 on the bottom and then an addition bracket. im thinking the closed formula for $\sum_{k=1}^nn(n+1)(n+2)\dots(n+k-1)\;;$ would be $\frac1{k+1}(n+k-1)$ im not too sure –  Matt Oct 23 '12 at 22:40
    
@Matt: Look at the closed forms in $(1)$ again: your $\frac1{k+1}$ is fine, but you should have $k$ more factors, not just one. –  Brian M. Scott Oct 23 '12 at 22:47
    
Im thinking something $\frac1{k+1}n(n+k)$ but not sure how to 'repeat' brackets for more terms of $k$. so for $k=1$ it works as it gives $\frac12n(n+1)$ but then for $k=2$ all i get it $\frac13n(n+2)$ rather than $\frac13n(n+1)(n+2)$ –  Matt Oct 23 '12 at 22:52
    
@Matt: When $k=1$ the RHS has two factors involving $n$; when $k=2$ it has three factors involving $n$; and when $k=3$ it has four factors involving $n$. In each case the smallest is $n$ and the largest is $n+k$. In the general case, then you should expect to have $k+1$ factors involving $n$, running from $n$ up through $n+k$. –  Brian M. Scott Oct 23 '12 at 22:57
    
So it is simply $\frac1{k+1}(n+k)$ –  Matt Oct 23 '12 at 23:01

If you divide both sides by $k!$ you will get binomial coefficients and you are in fact trying to prove $$\binom kk + \binom{k+1}k + \dots + \binom{k+n-1}k = \binom{k+n}{k+1}.$$ This is precisely the identity from this question.

The same argument for $k=3$ was used here.


Or you can look at your problem the other way round: If you prove this result about finite sums $$\sum_{j=1}^n j(j+1)\dots(j+k-1)= \frac{n(n+1)\dots{n+k-1}}{k+1},$$ you also get a proof of the identity about binomial coefficients.

share|improve this answer

From (i), (ii) and (iii) it is reasonable to guess that your sum will be $$n(n+1)\cdot...\cdot(n+k)/(k+1)$$ Try to prove this by induction.

share|improve this answer

For a fixed non-negative $k$, let $$f(i)=\frac{1}{k+1}i(i+1)\ldots(i+k).$$ Then $$f(i)-f(i-1)=i(i+1)\ldots(i+k-1).$$ By telescoping,

$$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)=\sum_{i=1}^n\left(f(i)-f(i-1)\right)=f(n)-f(0)=f(n)$$

and we are done.

share|improve this answer

Your Answer

 
discard

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.