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.

It is easy to show that

$$\sum _{i=1}^n (n+1-i) (n-i) = n (n-1)+(n-1) (n-2)+...+1 (1-1)=\frac{1}{3} \left(n^3-n\right)$$

using induction. But how do I derive this formula? I couldn't find any substitution to do this.

share|improve this question

5 Answers 5

up vote 8 down vote accepted

If you don't know/remember/want to use any of these "standard identities", then my favorite way is using finite differences. We can work directly with your original sum. Let's define

$$f(n)=\sum_{i=1}^n (n+1-i)(n-i).$$

First compute a bunch of values of $f$ like $f(1),f(2),f(3),...,f(10)$ for example. Then compute their finite differences. Then compute the second order finite differences, meaning finite differences of the finite differences. Then the third order and so on. You will see that eventually the finite differences are all zero. In this case the fourth order differences will all be zero. No matter how many terms you take, you can go up to $f(100)$ and they will all be zero.

This then tells you that $f(n)$ is a cubic polynomial in $n$. Then you simply compute any four (different) values, the easiest are using $f(1),f(2),f(3),f(4)$ and then get the unique interpolating polynomial that goes through those four points and then WHAM, you get your polynomial

$$f(n)=\frac{n^3-n}{3}.$$

The summation will always be a polynomial in $n$ if the summand is a polynomial in the index $i$ which means that eventually the finite differences will be zero. Specifically, the degree of $f(n)$ will be one higher than the degree of the summand in $i$ so in this we can also just look at the sum at see that the answer must be cubic in $n$.

Then just use interpolation to figure it out. This technique of finite differences is very powerful by the way and useful with all sorts of stuff. They (almost) mimic the continuous derivative. So for a polynomial, finite differences eventually become all zeros and hence stay zeros after that and the order when they first become all zeros tells you the degree of the polynomial. The fourth derivative of a cubic is zero so if fourth order finite differences of a sequence are all zeros then the generating function must be a cubic. For example, if you get the same exact (non-zero) differences like

$$1,2,4,8,16,...$$

$$1,2,4,8,16,...$$

then your original expression must be an exponential. Compare this with the derivative of an exponential being itself properly scaled. Derivatives of exponentials are never identically zero.

share|improve this answer
2  
Great method! Works on all polynomials and very simple. Thank you! –  Max Feb 28 '13 at 14:37
1  
If you look at your summand, it is quadratic in $i$, so you know the sum has to be cubic in $n$ (sums behave somewhat like integrals: $\sum_k k^m \rightsquigarrow n^{m + 1}$ just as $\int x^m d x \rightsquigarrow x^{m + 1}$) –  vonbrand Feb 28 '13 at 17:26

$$\sum _{i=1}^{n}{(n+1-i)(n-i)}=\sum _{i=1}^{n}{i(i-1)}=2\sum _{i=1}^{n}{\binom{i}{2}}=2\binom{n+1}{3}$$

This and related identities are easy to derive from the combinatorial identity

$$\sum_{i=0}^{n}{\binom{i}{k}}=\binom{n+1}{k+1}$$

share|improve this answer

You must already know that

$$ \begin{align} \sum_{i = 1}^n 1 &= n \\ \sum_{i = 1}^n i &= \frac{n(n + 1)}{2} \\ \sum_{i = 1}^n n &= n \cdot \sum_{i = 1}^n 1 \\ & = n^2 \\ \sum_{i = 1}^n i^2 &= \frac{n(n + 1)(2n + 1)}{6} \\ \end{align} $$

Now, from the given expression;

$$ \begin{align} \sum_{i=1}^n (n+1-i) (n-i) &= \sum_{i = 1}^n\left( n^2 + i^2 + n - i - 2 n i\right) \\ &= n^2 \cdot \sum_{i=1}^n 1 + \sum_{i=1}^n i^2 + n \cdot \sum_{i=1}^n1 - \sum_{i=1}^ni -2n \cdot \sum_{i=1}^ni \\ &= n^3 + \frac{n(n + 1)(2n + 1)}{6} + n^2 - \frac{n(n + 1)}{2} - n^2(n + 1) \\ &= \frac{n(n + 1)}{6} \cdot \left( 2n + 1 - 3\right) \\ &= \frac{n (n + 1)}{6} \cdot 2(n - 1) = \frac{n (n + 1) (n - 1)}{3} \\ &= \frac{n^3 - n}{3} \end{align} $$

share|improve this answer

Let me give you a hint for a combinatorial proof.

Let us say, we have $n+1$ integers from $1,2,3\cdots n,n+1$ and we need to pick $3$ integers from them.

How many ways to pick them. $\binom{n+1}{3}$.

Now, count the same as follows. What can be the largest integer of the selected $3$ element group. It can be any one of

3,4,5....n+1
. Let us count how many possible $3$ subset groups can have the largest element as $n+1$. It is $\binom{n}{2}$( agreed ). Like this, count all possible $3$ subset groups of $n+1$.

$\binom{n+1}{3} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \cdots \binom{n}{2}$

A little algebraic manipulation will do from here( divide by $2$ ).

share|improve this answer

Hint: $$ \sum_{i=1}^n i = \frac{n(n+1)}{2} $$ and $$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$ Now expand $(n+1−i)(n−i)$...

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.