Mathematical Induction and Strong Induction

PDF Download

Induction

Use induction when you are asked to prove a statement involving a natural number \(P(n)\), for all natural numbers (e.g. Show \(2n-1\) is odd for all \(n\in\mathbb{N}\)).

There are two parts to induction: Base Case and Induction Step

  1. In the base case, we show \(P(n)\) true for a starting value, usually \(P(1).\)
  2. In the induction step we show that if  \(P(n)\) works for a certain number \(\text{k}\) it will also work for the next number \(\text{k+1}\) (your prove \(P(k)\Rightarrow P(k+1)\) ). That is, you assume \(P(k)\) is true and use it to show that \(P(k+1)\) is also true. The statement \(P(k)\) is called the induction hypothesis.

Example

Prove that \(\sum_{i=1}^ni^3=\left(\frac{n(n+1)}2\right)^2\) for all \(n\in\mathbb{N}\).

Solution

Since we are being asked to prove something for all natural numbers, we will use induction. Here \(P(n)\) means \(\sum_{i=1}^ni^3=\left(\frac{n(n+1)}2\right)^2\).

  1. Base Case: 
    \(P(1)\) means \(\sum_{i=1}^1\boldsymbol{i}^3=\left(\frac{1(1+1)}2\right)^2\) ; check that the two sides are equal: \(\sum_{i=1}^1i^3=1^3=1\) and \(\left(\frac{1(1+1)}2\right)^2=\left(\frac22\right)^2=1.\) Therefore, \(P(1)\) is true.

  2. Induction Step:

    Induction hypothesis:

    Assume \(P(k)\) is true, that is \(\sum_{i=1}^k\boldsymbol{i}^3=\Bigg(\frac{k(k+1)}2\Bigg)^2.\) We will be using this fact in our proof.

    Now, we must prove \(P(k+1)\), that is \(\sum_{i=1}^{k+1}i^3=\left(\frac{(k+1)((k+1)+1)}2\right)^2.\) 

    We will start with the left side and show that it is equal to the right side. First expand the left side:

    \(\begin{gathered}
    \sum_{i=1}^{k+1}i^3 =1^3+...+k^3+(k+1)^3 \\
    =\sum_{i=1}^ki^3+(k+1)^3 
    \end{gathered}\)

    Notice that \(\sum_{i=1}^ki^3\) is a part of our hypothesis, we replace it with \(\left(\frac{k(k+1)}2\right)^2.\)

    \(=\left(\frac{k(k+1)}2\right)^2+(k+1)^3\)

    We use algebra to show that this is equal to the right side:

    \(\begin{aligned}
    \left(\frac{k(k+1)}2\right)^2+(k+1)^3& =(k+1)^2\Bigg(\frac{k^2}{4}+k+1\Bigg) \\
    &=\frac{(k+1)^2}4(k^2+4k+4) \\
    &=\frac{(k+1)^2(k+2)^2}4
    \end{aligned}\)

    We are done. Since we were able to show \(P(k)\Rightarrow P(k+1)\) and our base case, we conclude that \(\begin{aligned}&\sum_{i=1}^ni^3=&\left(\frac{n(n+1)}2\right)^2\\\\&.\end{aligned}\) for all \(n\in\mathbb{N}\).

Strong Induction

There are some statements \(P(n)\) about the natural numbers which regular induction cannot prove, in which case we must use Strong Induction. The main difference is that instead of \(\text{using only }P(k)\text{ to prove }P(k+1)\) we are allowed to use all of \(P(1)\),...,\(P(k)\) to prove it. We may not need all of them, but we assume they are all true.

We still have the same two steps, but they are slightly altered:

1. In the base case we prove more cases, the number depends on the question. Showing 3 base cases will be enough for most, usually \(P(1)\), \(P(2)\) and \(P(3)\).

2. In the induction step we assume \(P(1)\),...,\(P(k)\) are true and use them to prove \(P(k+1)\). That is, we prove \(P(1),...,P(k)\Rightarrow P(k+1).\)

Example

Assume that \(a_{n+1}=6a_{n-1}-12a_n+3\mathrm{~with~}a_1=1\mathrm{~and~}a_2=3_.\) Show that \({a}_n\) is odd for all \(n\in\mathbb{N}.\)

Solution

In this case \(P(n)\) is the statement \({a}_n\) is odd.

1. Base Case

  • \(P(1)\) means \({a}_1\) is odd; since \(a_1=1\) we know it is odd.
  • Similarly, \({a}_2=3\), is odd so \(P(2)\) is true.
  • To check \({a}_3\) we must use the recursive formula:
    \(\begin{aligned}&a_3=6a_2-12a_1+3\\&a_3=6(3)-12(1)+3\\&a_3=9\end{aligned}\)
    So \({a}_3\) is odd and \(P(3)\) is true.

   2. Induction Step:

Induction Hypothesis:

Assume that for some \(k\in\mathbb{N}\) we have that \(P(1),P(2),...,P(k-1),P(k)\) are all true. That is \(a_1,a_2,...,a_{k-1},a_k\) are all odd. We will be using this fact in our proof.

Now, we must prove \(P(k+1)\) is true. That is, \(a_{k+1}\) is odd. To talk about \(a_{k+1}\) we must use the recursive formula: \(a_{k+1}=6a_{k-1}-12a_k+3.\)

What do we know about \(a_{k-1}\) and \({a}_k\)? The induction hypothesis says they are odd! We can write them as \(a_{k-1}=2x+1\text{ and }a_k=2y+1\text{ with }x,y\in\mathbb{Z}.\) Let’s use these in the formula and try to show  \(a_{k+1}\) is odd. We are looking to express \(a_{k+1}\) as \(a_{k+1}=2(\sim)+1\) where ~ is an integer. 

\(\begin{aligned}
&\ {a}_{k+1} =6(2x+1)-12(2y+1)+3 \\
&\ {a}_{k+1} =6(2x+1)-12(2y+1)+2+1 \\
&a_{k+1} =2\left[3(2x+1)-6(2y+1)+1\right]+1 
\end{aligned}\)

Since \(3(2x+1)-6(2y+1)+1\) is an integer, \(a_{k+1}\) must be odd.

Therefore, by strong induction \({a}_n\) is odd for all \(n\in\mathbb{N}.\)