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:
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
Whereas if we had just plugged (k+1) into our formula, we still would end up with
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
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,
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
Adding all the red numbers gives us F2k .As we know, to get the next term in the Fibonacci sequence, we add the 2 previous terms. As such, to get the term F2k+2, we add F2k and F2k+1. so
F2k+ F2k+1 = F2k+2
But we already defined F2k as the sum of all those other Fibonacci numbers, and as such:
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.