Proof by induction for an unknown function, e.g. $\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = \frac{n}{6} - \frac{1}{6n}$

Question

I get how to do a proof by induction for say, a sum of all numbers or a sum of all numbers^2 function. But where do I start with a problem like:

$$\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = \frac{n}{6} - \frac{1}{6n}$$

So the function is (k-1)\cdot (n-k-1) but then the entire sum is over $n^2$.

And I'm told the answer will require me to make use of the sum of all numbers and sum of all numbers^2 functions:

$$\sum_{k=0}^n k = \frac{n\cdot (n+1)}{2}$$

$$\sum_{k=0}^n k^2 = \frac{n(n+1)\cdot (2n+1)}{6}$$

Which I thought I'd use by plugging in $\frac{n\cdot (n+1)}{2}$ for all the k's in the problem, but no luck. So I tried expanding the problem's function, so I can plug in the $k^2$ thing as well, but that doesn't seem to simplify properly either. Am I just going completely wrong with this?

The sheer number of brackets makes the question confusing to read... — , Mar 09 '14 at 19:34
Why did you change it back to the original version, without MathJax? @Mathster had formatted it correctly! — , Mar 09 '14 at 19:43
Sorry I didn't understand what it was T_T Changed the formula back a little though, is it better now? If it isn't obvious, I've never used latex or anything before :$ — MeltyButter, Mar 09 '14 at 19:45

score 0 · Accepted Answer · answered Mar 09 '14 at 20:09

0

In $$\sum_{k=0}^n\frac{(k-1)(n-k-1)}{n^2}=\frac n6-\frac 1{6n}$$ we can multiply through by $n^2$ to obtain$$\sum_{k=0}^n(k-1)(n-k-1)=\frac {n^3}6-\frac n6=\frac {n^3-n}6$$ as the target result you want to prove. The sum on the left then splits as$$\sum_{k=0}^n(k-1)(n-k-1)=n\sum_{k=0}^n(k-1) - \sum_{k=0}^n(k^2-1)$$

answered Mar 09 '14 at 20:09

Mark Bennet

100,194

sick, that works out :) – MeltyButter Mar 09 '14 at 21:34

Proof by induction for an unknown function, e.g. $\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = \frac{n}{6} - \frac{1}{6n}$

1 Answers1