Proof by induction: formula for the sum of i^2 from i = 1 to n, step by step

Femtobytes

femtobytes.com/solve/induction-sum/0_1_0_0

The problem

Find a closed formula for this sum and prove it for every natural number $n$ by induction.

\sum_{i=1}^{n} i^{2}

The result

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

Proved by mathematical induction: the formula holds for every natural number $n$ .

checked 16 lines of this solution were evaluated with exact arithmetic before it was shown to you. A solution with a false line is never served.

Picture 1 of 7Step 1: Say exactly what is claimed, and for which n

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Say exactly what is claimed, and for which n

Why this step

A formula with an $n$ in it is not one statement. It is an endless list of statements, one for each natural number, and no amount of checking examples can reach the end of an endless list. Before choosing a method we must see the claim for what it is: infinitely many claims wearing one coat.

The symbol $\sum$ (capital sigma) means "add up". $\sum_{i=1}^{n} i^{2}$ says: let $i$ run through $1, 2, 3, \ldots, n$ , work out $i^{2}$ for each, and add the results. The first few terms are $1 + 4 + 9 + 16 + \cdots$ .

S_n: \qquad \sum_{i=1}^{n} i^{2} = \frac{n \left( n + 1 \right) \left( 2 n + 1 \right)}{6}

Call this statement

S_n

. We must prove

S_1, S_2, S_3, \ldots

, every one of them.

$n$	term added	sum so far	formula
$1$	$1$	$1$	$1$
$2$	$4$	$5$	$5$
$3$	$9$	$14$	$14$
$4$	$16$	$30$	$30$
$5$	$25$	$55$	$55$
$6$	$36$	$91$	$91$

The sum added up by hand against the formula, for the first six n. They agree, which is encouraging and proves nothing about n = 7.

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Basis step: check the first statement

Why this step

The inductive step alone proves nothing: a chain of perfectly sound links hanging from no hook holds nothing up. There are famous false formulas whose inductive step works and whose first case fails. So we knock the first domino over by hand. With $n = 1$ the sum has a single term, so both sides are plain arithmetic.

\displaystyle \sum_{i=1}^{1} i^{2}

=

\displaystyle 1^{2}

With

n = 1

the only value of

i

1

, so the sum is its first term alone. checked

=

\displaystyle 1

Work it out. checked

\displaystyle \text{formula at } n = 1

=

\displaystyle \frac{1 \left( 1 + 1 \right) \left( 2 \cdot 1 + 1 \right)}{6}

Put

n = 1

into the formula. checked

=

\displaystyle \frac{1 \cdot 2 \cdot 3}{6}

Work out each bracket. checked

=

\displaystyle 1

Multiply, then divide. checked

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Inductive hypothesis: suppose one statement holds

Why this step

We now build the link between neighbouring dominoes. To do that we pick ONE unspecified natural number $k$ and suppose its statement holds. We use the letter $k$ rather than $n$ on purpose: $n$ belongs to the claim we are proving for all numbers, while $k$ is a single fixed number we are standing on.

S_k: \qquad \sum_{i=1}^{k} i^{2} = \frac{k \left( k + 1 \right) \left( 2 k + 1 \right)}{6}

Suppose this is true for some natural number

k \ge 1

. This is the inductive hypothesis. From here to the end of the inductive step we may use it freely.

S_{k+1}: \qquad \sum_{i=1}^{k+1} i^{2} = \frac{\left( k + 1 \right) \left( \left( k + 1 \right) + 1 \right) \left( 2 \left( k + 1 \right) + 1 \right)}{6}

This is what we must now DERIVE. It is

S_n

with every

n

replaced by

k + 1

. We are not allowed to use it, only to arrive at it.

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Work out the new term that statement k + 1 adds

Why this step

The sum up to $k + 1$ is the sum up to $k$ plus exactly one more term, the one with $i = k + 1$ . Everything in the inductive step turns on that single extra term, so we put it in a usable form first, as a polynomial in $k$ .

\displaystyle \left( k + 1 \right)^{2}

=

\displaystyle k^{2} + 2 k + 1

Multiply out the square:

(k + 1)^2 = k^2 + 2k + 1

. checked

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Inductive step, left side: start from the longer sum

Why this step

We must reach $S_{k+1}$ , whose left side is the sum up to $k + 1$ . The only fact we own is about the sum up to $k$ . So the first move is forced: split the longer sum into the part we know about plus the new term. That is the doorway through which the hypothesis enters.

\displaystyle \sum_{i=1}^{k+1} i^{2}

=

\displaystyle \left( \sum_{i=1}^{k} i^{2} \right) + \left( k + 1 \right)^{2}

Peel off the last term, the one with

i = k + 1

. What is left is exactly the sum up to

k

. checked

=

\displaystyle \frac{k \left( k + 1 \right) \left( 2 k + 1 \right)}{6} + \left( k + 1 \right)^{2}

The inductive hypothesis

S_k

: replace the sum up to

k

by the formula. THIS is the only place the hypothesis is used, and without it the proof could not move. checked

=

\displaystyle \frac{k \left( k + 1 \right) \left( 2 k + 1 \right)}{6} + k^{2} + 2 k + 1

The new term in the form found in the previous step. checked

=

\displaystyle \frac{k \left( k + 1 \right) \left( 2 k + 1 \right) + 6 \left( k^{2} + 2 k + 1 \right)}{6}

Give both parts the bottom

6

: multiply the new term top and bottom by

6

, then add the tops. checked

=

\displaystyle \frac{\left( k^{2} + k \right) \left( 2 k + 1 \right) + 6 k^{2} + 12 k + 6}{6}

Multiply the new term's bracket by

6

. Multiply the first two factors together. checked

=

\displaystyle \frac{2 k^{3} + 3 k^{2} + k + 6 k^{2} + 12 k + 6}{6}

Multiply out what remains of the product. checked

=

\displaystyle \frac{2 k^{3} + 9 k^{2} + 13 k + 6}{6}

Collect like powers of

k

. checked

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Inductive step, right side: multiply out the target

Why this step

We are aiming at the formula with $k + 1$ in place of $n$ . Rather than guess how to factor our long expression into that, we walk toward it from the other end: multiply the target out completely. If the two walks meet at the same polynomial, the two sides are equal. Meeting in the middle is honest and it never requires a lucky guess.

\displaystyle \frac{\left( k + 1 \right) \left( \left( k + 1 \right) + 1 \right) \left( 2 \left( k + 1 \right) + 1 \right)}{6}

=

\displaystyle \frac{\left( k + 1 \right) \left( k + 2 \right) \left( 2 k + 3 \right)}{6}

Tidy each bracket: for example

(k + 1) + 1 = k + 2

. checked

=

\displaystyle \frac{\left( k^{2} + 3 k + 2 \right) \left( 2 k + 3 \right)}{6}

Multiply the first two factors together and collect like powers. checked

=

\displaystyle \frac{2 k^{3} + 9 k^{2} + 13 k + 6}{6}

Multiply out what remains and collect like powers. checked

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Conclusion

Why this step

We have the two ingredients the principle of induction asks for, and nothing else is needed. It is worth saying plainly what each one contributed, because a proof by induction that skips this sentence has not finished.

The basis step showed $S_1$ is true. The inductive step showed that for every natural number $k$ , if $S_k$ is true then $S_{k+1}$ is true. So $S_1$ gives $S_2$ , which gives $S_3$ , which gives $S_4$ , and so on without end: by the principle of mathematical induction, $S_n$ is true for every natural number $n$ .

Each bar is the sum so far; the bright cap on top of it is the newest term, the one the inductive step adds. The dots are the formula. Every dot sits exactly on top of its bar.

Proof by induction for a sum