Page 56 - 'Blast_Into_Math

Blast into Math! ets of nummers: mathematical plaagrounds

• therefore, the statement is true for n =2, but then, the mathemagic starts to work, because
once the statement is true for n =2, it must also be true for n =3, and then for n =4,
and it continues to be true for all positive integers.

So, the mathemagical induction escalator brings us higher and higher, and the escalator never stops!

Let’s now go through the three steps to prove Gauss’s formula by induction:

n(n +1)
We want to prove: 1+2+ ... + n = ∀ n ∈ N.
2

First we’ll try putting a foot on the escalator: that’s the base case.

1. Base Case: Is this statement true when n =1? Let’s check:

1(1+ 1)
1= ,
2

yes, that is true.

2. Induction assumption: we assume the formula holds for some n ≥ 1. So at this point we
have assumed
n(n +1)
1+2+ ... + n = .
2

3. Proof: we must use the induction assumption to show that the formula will be true for the
next integer, n +1, in other words, we must show

(n +1)(n +1+1)
1+2+ ... + n +(n +1)= .
2

To do this, we use step 2. We can split the sum on the left side above into the first n numbers
and then the last one,

(1 +2 + ... + n)+ n +1.

We already know that, by the induction assumption, (Step 2)

n(n +1)
1+2+ ... + n = ,
2

56