Proof by Mathematical Induction

30 Apr 2014

Maths


Providing proof by Mathematical Induction allows us to prove that a recursive function will return the correct value for any value within its sequence.

It's possible to use mathematical induction to prove that an algorithm will function correctly for all values passed into it, however I've found the approach favoured by pretty much everyone when first learning how to use mathematical induction often confuses the situation. Many approaches have you rewriting equations for `k` or something else, and I've found this to detract from the task at hand.

We still need to perform the following steps in order to provide proof:

  1. Prove the basis step
  2. Assume that the function is correct
  3. Prove that function holds by the addition of `1`

My method for this is simple, but involves taking a step back and abstracting the equation slightly:

  1. Rewrite the basis step using abstracted terms: `A = B`
  2. Rewrite the inductive step using the abstracted terms: `(A + 1) + B = (B + 1)`
  3. Solve for the Left Hand Side: `(A + 1) + B`
    1. Solve `(A + 1)`
    2. Add `(A + 1)` to `B`
  4. Solve for the Right Hand side: `(B + 1)`

Example 1

Consider the following:

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

Proving that this function is correct for the basis step is relatively easy, we replace all instances of `n` with the first number in the sequence, which in this instance is `1`:

`n = 1`

`1 = 1 * (1 + 1)/2`

`=> 1 = 1 * (2)/2`

`=> 1 = 2 / 2`

`=> 1 = 1`

`=> True`

We have proved that `A = B` for the basis step.

Now, we add one to `1` to the function and check it again. Our equation will now look like this:

`(n + 1) = (n + 1) * ((n + 1) + 1)/2`

Note that we've replaced every instance of `n` with `(n + 1)`.

Normally, you would now have to rewrite the equation for `k` (or something else), however I believe that my approach is simpler to understand. If we generalise the original equation slightly, the form of the basis step then becomes:

`A = B`

Now, if we rewrite the inductive step using the same generalised terms, then:

`(A + 1) + B = (B + 1)`

All we need to do now is rewrite the generalised terms and solve:

`(A + 1)` - replace instances of `n` with `(n + 1)`

`=> (n + 1)`

`B`

`=> n * (n + 1)/2`

`(B + 1)` - replace instances of `n` with `(n + 1)`

`=> (n + 1) * ((n + 1) + 1)/2`

Now it's possible to solve the inductive step by checking if `(A + 1) + B = (B + 1)`.

Left Hand Side

`(A + 1) + B`

`=> (n + 1) + n * (n + 1)/2`

`=> 2(n + 1)/2 + n * (n + 1)/2`

`=> 2n + 2 + n^2 + n/2`

`=> n^2 + 3n + 2/2`

Right Hand Side

`(B + 1)`

`=> (n + 1) * ((n + 1) + 1)/2`

`=> (n + 1) * (n + 2)/2`

`=> n(n + 2) + 1(n + 2)/2`

`=> n^2 + 2n + n + 2/2`

`=> n^2 + 3n + 2/2`

As both sides of the equation match, we have provided proof by induction.


Example 2

Consider the following:

`1^2 + 2^2 + 3^2 + ... + n^2 = n(n + 1) * (2n + 1)/6`

Prove the basis step:

`n = 1`

`=> 1^2 = 1(1 + 1) * (2(1) + 1)/6`

`=> 1 = 1(2) * (2 + 1)/6`

`=> 1 = 1(2) * (3)/6`

`=> 1 = 1* (6)/6`

`=> 1 = 6/6`

`=> 1 = 1`

`=> True`

We have proved that `A = B` for the basis step.

Now, if we rewrite the inductive step using abstracted terms, then:

`(A + 1) + B = (B + 1)`

Rewrite the Left Hand Side with abstracted terms:

`(A + 1)` - replace instances of `n` with `(n + 1)`

`=> (n + 1)^2`

`B`

`=> n(n + 1)(2n + 1)/6`

`(B + 1)` - replace instances of `n` with `(n + 1)`

`=> (n + 1)((n + 1) + 1) * (2(n + 1) + 1)/6`

Now it's possible to solve the inductive step by checking if `(A + 1) + B = (B + 1)`.

Left Hand Side

`(A + 1) + B`

`=> (n + 1)^2 + n(n + 1) * (2n + 1)/6`

`=> (n + 1)(n + 1) + (n^2 + n) * (2n + 1)/6`

`=> n(n + 1) + 1(n + 1) + n^2(2n + 1) + n(2n + 1)/6`

`=> (n^2 + n + n + 1) + (2n^3 + n^2 + 2n^2 + n)/6`

`=> 6(n^2 + 2n + 1)/6 + (2n^3 + 3n^2 + n)/6`

`=> 6n^2 + 12n + 6/6 + 2n^3 + 3n^2 + n/6`

`=> 2n^3 + 6n^2 + 3n^2 + 12n + n + 6/6`

`=> 2n^3 + 9n^2 + 13n + 6/6`

Right Hand Side

`(B + 1)`

`=> (n + 1)((n + 1) + 1) * (2(n + 1) + 1)/6`

`=> (n + 1)(n + 2) * ((2n + 2) + 1)/6`

`=> (n + 1)(n + 2) * (2n + 3)/6`

`=> n(n + 2) + 1(n + 2) * (2n + 3)/6`

`=> (n^2 + 2n + n + 2) * (2n + 3)/6`

`=> (n^2 + 3n + 2) * (2n + 3)/6`

`=> 2n(n^2 + 3n + 2) + 3(n^2 + 3n + 2)/6`

`=> 2n^3 + 6n^2 + 4n + 3n^2 + 9n + 6/6`

`=> 2n^3 + 6n^2 + 3n^2 + 9n + 4n + 6/6`

`=> 2n^3 + 9n62 + 13n + 6/6`

As both sides of the equation match, we have provided proof by induction.


 

Copyright © 2024 carlbelle.com