# Proof by induction

1. Oct 30, 2005

I am supposed to prove a conjecture by induction. I have worked out that the series can be described by:

a = 2,6,12,20,30
S = 2+8+20+40....

(n^2) + n = (1/3) ((n^3)+3(n^2)+2n)

However, i cannot prove it by induction. It seems like there is smth wrong with the K^3.

2. Oct 30, 2005

### Muzza

What series? And what precisely is it that you want to prove? I doubt that you actually want to prove that (n^2) + n = (1/3) ((n^3)+3(n^2)+2n), because that's not true (for all n).

3. Oct 30, 2005

### benorin

This should help

I think Link means $$\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)$$, which is in fact true.
The inductive proof goes like this:
i. $$\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)$$ , holds for $$n=1$$;
ii. Assume $$\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)$$ holds for some fixed n, so that
$$\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)\Rightarrow \sum_{k=1}^{n} \left(k^2 + k\right) + \left((n+1)^2 + (n+1)\right) = \frac{1}{3}(n^3+3n^2+2n) + \left((n+1)^2 + (n+1)\right)$$
$$\Rightarrow \sum_{k=1}^{n+1} \left(k^2 + k\right) = \frac{1}{3}(n^3+6n^2+11n+6) = \frac{1}{3}\left((n+1)^3+3(n+1)^2+2(n+1)\right)$$.
Therefore, $$\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)$$ holds for every positive integer n.

Last edited: Oct 30, 2005
4. Nov 6, 2005

thanks! but there is another problem arising from this, regarding the interpretation of a question.

Based on the results obtained above, how can i calculate 1^2 + 2^2 + 3^2.....+n^2?

the problem is the word "calculate", do you think they want me to use the same method to derive a general expression for this series, or actually get an numerical value (i dont think its obtainable)? Im the only one in class doin this investigation and I cannot reach my teacher this week so advice on the meaning of this is appreciated.

5. Nov 6, 2005

### HallsofIvy

Staff Emeritus
Well, you now know that
$$\sum_{k=1}^{n} \left(k^2 + k\right)=\sum_{k=1}^nk^2+ \sum_{k=1}^nk = \frac{1}{3}(n^3+3n^2+2n)$$
If you know a formula for
$$\sum_{k=1}^{n} k$$
just subtract that from both sides.