Induction in mathematics

In mathematics, there is a type of proof called induction. This is not to be confused with inductive reasoning--this is an entirely different concept which just happens to have similar etymology.

So let's say I wanted to prove the below equation for all natural numbers n. (The natural number are {1, 2, 3, 4, 5, ... }.)

1 + 2 + 3 + ... + n = n*(n+1)/2

First, let's test the equation for a few values of n.

1 = 1*(1+1)/2 = 1
1 + 2 = 2*(2+1)/2 = 3
1 + 2 + 3 = 3*(3+1)/2 = 6
1 + 2 + 3 + 4 = 4*(4+1)/2 = 10

So do you get the idea? But how do we prove that the equation is true for all n? There are infinite natural numbers, so we can't just go through them one by one.

What we use is a method called induction. First, we prove that the equation is true for n = 1. Second, we show that if it is true for n = k, it is also true for n = k+1. After we have proven this, we know that the equation is true for n = 1, and therefore n = 2, and therefore n = 3, and so on. The equation is true for n = {1, 2, 3, 4, 5, ...} = all natural numbers. It's that easy.

So here goes:
Step 1: 1 = 1*(1+1)/2 = 1
Step 2:
Assume: 1 + 2 + 3 + ... + k = k*(k+1)/2
Show: 1 + 2 + 3 + ... + k + (k + 1) = (k+1)*(k+2)/2
k*(k+1)/2 + (k+1) = k*(k+1)/2 + 2*(k+1)/2
Therefore, the statement "1 + 2 + 3 + ... + n = n*(n+1)/2" is true for all natural numbers n.

Here's a more complex example. Consider the Fibonacci Sequence, which goes {1,1,2,3,5,8,13,...}. Each number is the sum of the previous two numbers. Let's say that I've given you the following equation:

F(n) = nth Fibonacci number = (Φⁿ - (-Φ)^-n) / sqrt(5)
where Φ = 1/2 + sqrt(5)/2 This number is called the golden ratio.

How can you prove this equation is true for all natural numbers? First, you prove it for n=1 and n=2. Then, you show that if it's true for n = k and n = k+1, it must also be true for n = k+2.

But the actual proof might be too messy for a blog post ... so I leave it as an exercise to the reader (this is code for "I tried it, but I lost interest before finishing").

Anyways, the interesting thing about induction is that it only really helps you after you've found the equation for a sequence. Induction doesn't help in finding the equation itself. For example, if I hadn't given you the formula for the Fibonacci sequence, you would have nothing to work with. So how did I get that formula? The short answer is that I used mathematical intuition and a calculator.

So the moral that I'm tacking on here is that real math is not just the mindless execution of a bunch of instructions. Real math requires quite a bit of insight and intuition.