Page 51 - 'Blast_Into_Math

Blast into Math! ets of nummers: mathematical plaagrounds

3.4 Proof by induction

Induction can be used to prove a statement which is true for any positive integer. To learn how proof by
induction works, we’ll use induction to prove a formula which according to mathematical folklore, the
famous mathematician Carl Gauss realized when he was just seven years old. As the story goes, in primary
school Gauss and his classmates were playing rowdily and not minding their teacher. As punishment
for their unruly behavior, the teacher gave them an exercise to keep them busy and quiet for a long
time: add all the positive integers from 1 to 100. Each student was told to write his or her answer on a
slate and set the slate on a table. After just a few minutes, Gauss sprung from his seat, wrote his answer

on a slate and set it on the table. A long while later the next student stood from his seat and wrote his
answer on a slate, which he stacked on top of Gauss’s. One by one the students eventually all wrote their
answers on the slates and formed a great pile, with Gauss’s at the very bottom. To the teacher’s dismay,
the answer on each slate was wrong until the very last slate. Not only was Gauss the fastest, but also the
only student with the correct answer! How did he do it?

We can imagine that the playful young schoolboy Gauss thought about the problem as follows. He
wanted to play, but he could not. So, he imagined the numbers were playing the game of addition. As
he visualized the numbers playing addition, he knew of course that if you add the numbers in different
orders, the total sum will always be the same. Gauss saw the numbers as playful school children. There

were the bigger kids, like 100 and 99, and the smallest kids, 1 and 2, and then lots of kids in the middle.
But no matter which way they re-arranged themselves, they would always add up to the same total.
Suddenly, Gauss realized an especially fair way to play the game of addition. The numbers increase by
1 going from smallest to largest: 1, 2, 3, …, 98, 99, 100 , but the numbers decrease by 1 going from
largest to smallest: 100, 99, 98, ... , 3, 2, 1. So, if you add the smallest with the largest,

1+ 100 = 101.

The next smallest player is one larger than the smallest,

1+ 1= 2,

and the next largest player is one smaller than the largest,

100 − 1= 99.

When you add them,

2+ 99 = 101.

51