How do I prove by induction?

Question

For example if i wanted to prove: $1^2 + \dots + n^2 = \frac {n(n + 1)(2n + 1)} {6}$ by induction. I'm not sure where to start. Thanks.

Answer 1

Prove for the base case, n=1:

$$1^{2} = \frac{1(1+1)(2+1)}{6} = \frac{2\cdot3}{6}=1$$

The "sum" of just $1^2$ is indeed 1. Base case proven.

Now for the induction step, proving that it holds for n+1:

Observe that for $1^{2} + 2^{2} +... + n^{2}$, the sum including $n+1$ equals the original summation plus the $n+1$ term: $1^{2} + 2^{2} + ... + n^{2} + (n+1)^{2}$, i.e. equals $ \frac{n(n+1)(2n+1)}{6} + (n+1)^{2}$.

So all we need to do is show that $\frac{n(n+1)(2n+1)}{6} + (n+1)^{2} = \frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}$.

(Edit: To be clear: $\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}$ is $\frac{n(n+1)(2n+1)}{6}$ with $n+1$ substituted in for $n$.)

Let's do that now: $$\frac{n(n+1)(2n+1)}{6} + (n+1)^{2} = \frac{n(n+1)(2n+1)}{6} + \frac{6(n+1)^{2}}{6}$$ $$ = \frac{n(n+1)(2n+1)+6(n+1)^2}{6}$$ $$ = \frac{n(n+1)(2n+1)+6(n^{2}+2n+1)}{6}$$ $$ = \frac{n(2n^{2}+3n+1)+6n^{2}+12n+6)}{6}$$ $$ = \frac{2n^{3}+3n^{2}+n+6n^{2}+12n+6}{6}$$ $$ = \frac{2n^{3}+9n^{2}+13n+6}{6}$$

Having simplified this, we'll now show that it is equal to $\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}$:

$$\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6} = \frac{(n+1)(n+2)(2n+3)}{6}$$ $$ = \frac{(n^{2}+3n+2)(2n+3)}{6}$$ $$ = \frac{2n^{3}+6n^{2}+4n+3n^{2}+9n+6}{6}$$ $$ = \frac{2n^{3}+9n^{2}+13n+6}{6}$$

And we're done!

Answer 2

Although this is not induction, I still find it quite amusing that Leibniz (inventing the differential calculus almost simultaneously with Newton) solved these kind of problems with some sort of difference method with great similarity to his differential calculus:

First we define the differences of a sequence: For instance the sequence $x^2$ for integers $x$ has (first order) differences $$ dx^2=(x+1)^2-x^2=2x+1 $$ or more generally $f:\mathbb Z\rightarrow\mathbb Z$ has differences $df=f(x+1)-f(x)$ in modern function notation. With this definition it can be seen (using the binomial theorem) that $$ \begin{align} dx^4&=4x^3+6x^2+4x+1\\ dx^3&=3x^2+3x+1\\ dx^2&=2x+1\\ dx&=1\\ d(kf)&=k\ df\\ dk&=0 \end{align} $$ where $k$ denotes some constant. One notices that taking differences of polynomial expressions yields polynomials of one degree less.

Now your problem corresponds to saying $df=(x+1)^2=x^2+2x+1$ and searching for a polynomial expression $f(x)$ solving this. From the degree it follows that $$ f(x)=ax^3+bx^2+cx+d $$ Therefore $$ \begin{align} x^2+2x+1&=df\\ &=a(3x^2+3x+1)+b(2x+1)+c\\ &=3ax^2+(3a+2b)x+(a+b+c) \end{align} $$ Now to match coefficients of these two expressions for the same quadratic we must have $$ \begin{align} 3a&=1\\ 3a+2b&=2\\ a+b+c&=1 \end{align} $$ which is a system of linear equations that can be solved to get $a=\frac{1}{3}$, $b=\frac{1}{2}$ and $c=\frac{1}{6}$. The constant term $d$ can then be determined from the initial value $f(1)=1$ leading to $d=0$. So we have found that $$ \begin{align} f(x)&=\frac{1}{3}x^3+\frac{1}{2}x^2+\frac{1}{6}x\\ &{}\\ &{}\\ &=\frac{x(x+1)(2x+1)}{6} \end{align} $$ Both note how this method is constructive we do not need know the answer beforehand as it just jumps out from the method, but also how it has great similarities to integration of a function with a given initial value.

Answer 3

Since $\frac{1(1 +1)(2+1)}{6} = 1$, then base case holds. Suppose result holds for $n$. Then

$$\sum_{i=1}^{n+1} i^2 = \sum_{i=1}^{n}i^2 + (n+1)^2 = \frac{n(n+1)(2n + 1)}{6} + (n+1)^2 $$

$$ \frac{n(n+1)(2n + 1)}{6} + (n+1)^2 = \frac{(n+1)[n(2n+1) + 6(n+1)}{6} = \frac{(n+1)(2n^2 + 7n + 1)}{6} =_{*} \frac{(n+1)(n+2)(2n + 3)}{6} = \frac{(n+1)((n+1) + 1)(2(n+1) + 1)}{6} $$

(*): Since $2n^2 + 7n + 1 = (n+2)(2n+3)$. The problem is solved by math induction.