Proof by induction is one of the most prominent forms of proof. It’s often likened to mathematical dominoes – set the dominoes up, knock one down, and the rest fall as well. How does it work?

It’s quite hard to explain without an example, so I will look at it through the lens of finding a general formula for adding natural numbers.

Say I want to add up 1+2+3+4+5+6…+99+100. That’s a lot of adding – is there a shortcut formula? as it turns out, there is. adding up all the integers from 1 to “n” is equivalent to:

^{n(n+1)}⁄_{2}

So if we plug in “1” we get 1, “2” we get 1+2=3, and so on. But how do we prove this formula works? Well, we use induction! There are 2 main steps.

Firstly, let’s assume it works (rash, I know) for some number *k. *So

1+2+3+4…+k = ^{k(k+1)}⁄_{2}

Now we want to show that, if it works for k, it works for (k+1) as well. So we add k+1 to both sides:

1+2+3+4…+k+k+1 = ^{k(k+1)}⁄_{2} + k+1

= ^{(k(k+1)+2k+2)}⁄_{2}

= ^{(k(k+1)+2(k+1))}⁄_{2}

=^{(k+1)(k+2)}⁄_{2}

Whereas if we had just plugged (k+1) into our formula, we still would end up with

^{(k+1)(k+2)}⁄_{2}

So what have we shown? We’ve shown that, if our rule works for any value k, it also works for k+1, as you can add k+1 to both sides and get the same result. But then, as k+1 works, it must also work for k+2, and k+3, and k-1, and so on. All values of k must work (whole numbers, of course!)

There’s one snag however – we started assuming it works for some value k. If we find a single value of k for which it works, then all the other values of work. If we plug in 1, we get:

1 = ^{(1)(1+1)}⁄_{2} = 1

Since it works when k=1, it works for all other possible input values. As such, the sum of the numbers from 1 to n is

^{n(n+1)}⁄_{2}

Right, now that’s out of the way – To the Fibonacci!

So, we have the Fibonacci sequence

1,1,2,3,5,8,13,21,34,55,… (The initial 0 is removed for convenience)

And we’ve discovered this potentially interesting property – if you start from the first number, and add it to every second number for n steps (so you add the 1st, 3rd, 5th, 7th and so on, until you get to the (2n-1)th number, that sum is equal to the next number in the sequence, 2n. For example,

1,1,2,3,5,8,13,21

1+2+5+13=21

So we want to prove that this pattern holds. How? Induction! Let’s say that the rule hold when you add up the first *k* odd number terms of this sequence, for some specific value of *k*. This means that

1,1,2,3,5,8,13,…F_{2k-1},F_{2k}

Adding all the red numbers gives us F_{2k} .As we know, to get the next term in the Fibonacci sequence, we add the 2 previous terms. As such, to get the term F_{2k+2}, we add F_{2k} and F_{2k+1}. so

F_{2k}+ F_{2k+1} = F_{2k+2}

But we already defined F_{2k} as the sum of all those other Fibonacci numbers, and as such:

1,1,2,3,5,8,13,…F_{2k-1},F_{2k},F_{2k+1},F_{2k+2}

All the red numbers add up to the green one.

So we have shown that if it works for the first k terms, we can extend it to the next term (which is 2 further along, thus the jump from 2k to 2k+2). So if we can find a single value of k where it works, they all work. if we start with the very simple value for *k*, 1, then the sum is 1, and the 2nd term is 1, so we know it works, and via induction, it works for all integers.

## Leave a Reply