Mathematical Induction

What is mathematical induction:

Mathematical induction is a method of proving that a statement is true for all natural numbers. In the context of computer science, it can be used to prove that a recursive or incremental insertion algorithm is correct. 

Recursive or incremental algorithms can fall into two types of mathematical formulae:

• Arithmetic Progression - Difference between the sequence of numbers is constant. For example the sequence 2,4,6,8,10 (The difference between each number in the sequence is 2).

• Geometric Series - The ratio between the terms is constant or that each term is found by multiplying the previous by some constant.. For example the following sequence 2,4,8,16,32 (The sequence has a factor of 2 between each number)

How to do mathematical induction:

Mathematical induction comprises of proving that a conjecture is true by proving that the next element in the given formula is correct. It is only proven false through a counter example. 

In plain English induction is performed in the following steps:

1. Show that the statement works the first time
2. Assume that it works for this time
3. Show that it works for the next time
4. Conclusion is that it works all the time

The assumption with mathematical induction is that you accept it as true without solving it completely. If step 3 fails, then the assumption is wrong and the conjecture fails. 

In mathematical terms induction means:

1. Show that the statement is true when n = 1
2. Assume that it is true for n = k
3. Show that it is true for n = k + 1
4. Conclusion that it is true for all values n >= 1

Example:

Prove that 1 + 4 + 9 + …. + n² = n (n + 1)(2n + 1) / 6 for all positive integers n
In mathematical induction, before jumping right into the induction steps (outlined above), we’ll need to find the general term and n^th partial sum.

Step 1: Identify the general term and n^th partial sum:
    
The general term an is the last term on the left hand side (LHS) of the formula. In this case it’s n² therefore an = n².

The n^th partial sum, Sn is the right hand side (RHS) of the formula. In this case Sn = n (n + 1)(2n + 1) / 6.

Step 2: Find the next term in the general sequence and series:

The next term in the sequence is defined as a_{k + 1} and it is found by substituting n with k + 1 in the general term an that we found Step 1, therefore we’re left with the following:

a_{k + 1}  = (k + 1)²

The next term in the partial sum is S_{k + 1} and is found again by substituting n with k + 1 in the n^th partial sum an that we found in step 1, such that we’re left with:

S_{k+ 1} = (k + 1) (k + 1 + 1)(2(k + 1) + 1) / 6

= (k + 1)(k + 2)(2k + 3) / 6

Once we’ve completed these two steps, we can finally begin the induction process. Remember the 4 conditions that are outlined above, we’ll take the mathematical explanation here.

Begin the Induction...

Condition #1: Show that the statement is true for n = 1, show that a1 = S1. 

What we’re interested in here, is that we want to make sure that an = Sn when n = 1, all this means is that we substitute the value of 1 into both the general term and n^th partial sum that we found in Step 1.

LHS: a1 = 1² where, an = n²

RHS :  S1 = 1 (1 + 1)(2(1) + 1) / 6 

= 1 (2) (3) / 6

= 6 / 6

= 1, where Sn = n (n + 1)(2n + 1) / 6

From this we can see that a1 = S1 therefore satisfying condition 1, allowing us to continue the induction.

Condition #2: Assume that the original statement is true for n = k.

The LHS is the sum of the first k terms so we can write it as Sk. The RHS side is found by substituting n = k into Sn.

We assume that Sk = k (k + 1)(2k + 1) / 6

Condition #3: Show that the statement holds true for n = k + 1.

In this condition, we’re trying to show that S_{k+ 1} = (k + 1) (k + 2)(2k + 3) / 6. This is what we found in Step 2 before we began our induction process. To do this we begin by using the assumption from Condition #2 and accepting that it is true, and we add the next term a_{k + 1} (Which we found in Step 1) to both sides of the equation. 

Sk = k (k + 1)(2k + 1) / 6

a_{k + 1}  = (k + 1)²

thus Sk + a_{k + 1}  = k (k + 1)(2k + 1) / 6 + a_{k + 1}

The LHS Sk + a_{k + 1} means “the sum of the first k terms and the next term”, which will give us the sum of the first k + 1 terms. In other words, if k = 9, then S9 would be the sum of the first 9 terms and a_{k + 1} would be the 10^th term, the result being the sum of the first 10 terms. 

On the RHS, replace a_{k + 1} with its value (k + 1)².

Sk + a_{k + 1}  = k (k + 1)(2k + 1) / 6 +  a_{k + 1}.

Sk + 1  = k (k + 1)(2k + 1) / 6 + (k + 1)².

Now we need to factorise k (k + 1)(2k + 1) / 6 + (k + 1)² such that it equals our goal of (k + 1)(k + 2)(2k + 3) / 6 which we found from Step 2 to prove that the statement is true for n = k + 1.

Multiply (k + 1)² by 6/6 to obtain the common denominator:

Sk+1  = k (k + 1)(2k + 1) / 6 + 6(k + 1)² / 6

Now to factorise: 

 Sk+1  = (k+1) [k (2k + 1) + 6(k + 1)] / 6

Now to expand:

Sk+1  = (k+1)(2k² + k + 6k + 6) / 6

= (k + 1)(2k² + 7k + 6) / 6

Now to factorise again to see if we equal our goal

S_{k+ 1} = (k + 1)(k + 2)(2k + 3) / 6

Through Condition #3, we have proven that the formula holds true for n = k + 1. From this we move to Condition #4 which states that because Condition #3 is true, therefore the conclusion is that it is true for all values n >= 1.

Conclusion: 

Mathematical induction can be a tricky exercise when there are this many steps involved, however following the steps that are outlined can go a long way into understanding how it works. As with all things, the more practice you get, the easier it becomes. From this method we can prove through assumptions that certain algorithms are correct for all values without actually calculating every single value. 

Exercises:

1. Prove that i = n (n + 1) / 2 for all values of n >= 0 by induction.

2. Prove that i³ = n² (n + 1)² / 4 for n >= 0 by induction.

3. Prove that 1 + 3 + 5 + … 2n - 1 = n²

(Tip: Follow the same steps from above and don’t get tricked out by the “for n >= 0")