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

Femtobytes

femtobytes.com/solve/induction-sum/0_-1_-3_-1

The problem

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

\sum_{i=1}^{n} \left( -i^{2} - 3 i - 1 \right)

The result

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

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

checked 19 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 2Step 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} \left( -i^{2} - 3 i - 1 \right)$ says: let $i$ run through $1, 2, 3, \ldots, n$ , work out $-i^{2} - 3 i - 1$ for each, and add the results. The first few terms are $-5 - 11 - 19 - 29 + \cdots$ .

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

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$	$-5$	$-5$	$-5$
$2$	$-11$	$-16$	$-16$
$3$	$-19$	$-35$	$-35$
$4$	$-29$	$-64$	$-64$
$5$	$-41$	$-105$	$-105$
$6$	$-55$	$-160$	$-160$

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} \left( -i^{2} - 3 i - 1 \right)

=

\displaystyle -1^{2} - 3 \cdot 1 - 1

With

n = 1

the only value of

i

1

, so the sum is its first term alone. checked

=

\displaystyle -5

Work it out. checked

\displaystyle \text{formula at } n = 1

=

\displaystyle -\frac{1 \left( 1 + 2 \right) \left( 1 + 4 \right)}{3}

Put

n = 1

into the formula. checked

=

\displaystyle -\frac{1 \cdot 3 \cdot 5}{3}

Work out each bracket. checked

=

\displaystyle -5

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.

Proof by induction for a sum

Say exactly what is claimed, and for which n

Basis step: check the first statement

Inductive hypothesis: suppose one statement holds

Work out the new term that statement k + 1 adds

Inductive step, left side: start from the longer sum

Inductive step, right side: multiply out the target

Conclusion