Induction

Induction, hooray!

So this is one of the easiest proofs by induction to understand. And it's cool.

Suppose we wanted to add all the natural numbers from 1 to 100, what would we get? (1+2+3+...+99+100 = ??)

Don't reach for a calculator (or Excel spreadsheet) yet, that'd just be obnoxious, instead lets look at a simpler problem. What is the sum of the natural numbers from 1 to 5? 1+2+3+4+5 = 15. What about from 1 to 6? 21. Let's create a table of these sums:

1	1
2	3
3	6
4	10
5	15
6	21
7	28

On the left we have number, and on the right we have the sum of all the numbers from one to that number. Before going any further, see if you can detect a pattern in the right column.

One pattern is very obvious, to get the next number on the right column, all you have to do is add the number to its left to the number above it (7+21=28). So the next number down will be 28+8=36. In general we can write the formula:

F(n+1) = (n+1) + F(n)

This is a recursive formula, written in terms of the previous value. This is helpful, because if we know value, we can easily figure out what comes next, but it doesn't really help trying figure out what the 100th value is (unless we want to first figure out 99 others).

So while our recursive formula is nice, it's not nice enough. Some more observations might lead to:

F(n) = n(n+1)/2

(Side note: I gave this assignment to a group of nine sixth graders and they found this result on their own in under 45 minutes). Now to find all the numbers from 1 to n, all you have to do is multiply n by n+1 and divide that by 2. But is does that formula really work? Well now we finally get around to induction (I know it's taken a while).

To prove something by induction, we have to show it's true for the initial case, then show that if it's true for the nth case, it'll always be true for the (n+1)th case. The first step is easy:

F(1) = 1(1+1)/2 = 2/2 = 1

So our formula certainly holds true for the first case. Now assume that it's true for the nth case:

F(n) = n(n+1)/2

and if we add n to both sides of this equation we get:

F(n)+(n+1) = n(n+1)/2 +(n+1)

From our recursive function we get:

F(n+1) = n(n+1)/2 +(n+1)

Some algebra magic gives:

F(n+1) = n(n+1)/2 +2(n+1)/2 = (n²+n+2n+2)/2 = (n²+3n+2)/2 = (n+1)((n+1)+1)/2

Which is exactly what we would get if we plugged (n+1) in for every n.

So, the 100th number (our original goal) is:

F(100) = 100(101)/2 = 5050

Some final thoughts:

Can you figure out why these are called "triangular numbers?" (Googling = cheating)

I used heavy use of function notation here, if anyone has a problem with that, let me know.