Proof by Induction

Tags

math

Is a way to prove a mathematical theorem by firstly showing it holds for \( n=1 \), and then proving it holds for \( n=k+1 \) assuming it holds for \( n=k \). This shows that the property can hold for all \( n \geq 1 \) by induction.

Induction can be used to prove recurrence relations, infinite series, or divisibility.

Matrix Multiplication example

For example lets suppose that if \( T^n = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^n \) then \( T^{n} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} \) for all \( n \in \mathbb{N} \). To prove this we must:

1. Initial Step: Show it holds for \( n = 1 \).

   \begin{align*} LHS \longrightarrow T^1 &= \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \
   RHS \longrightarrow T^1 &= \begin{pmatrix} 1 & (1) \\ 0 & 1 \end{pmatrix} \
   \end{align*}

2. Construct a induction hypothesis. We assume that \[ T^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \]

3. Perform the induction step: Prove the theorem when \( n = k+1 \). We want to show that \( T^{k+1} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix} \).

   \begin{align*} LHS &= T^{k+1} \\

     &= T^k T \\\\
     &=
       \begin{pmatrix}
         1 & k \\\\
         0 & 1
       \end{pmatrix}
             \begin{pmatrix}
               1 & 1 \\\\
               0 & 1
             \end{pmatrix} \\\\
     &=
       \begin{pmatrix}
         1 & k+1 \\\\
         0 & 1
       \end{pmatrix} \\\\
     &= RHS

   \end{align*}

   We've shown that the left hand side matches the right hand side using the induction hypothesis therefore this theorem holds.

4. Write a conclusion:

   We checked it's true when \( n=1 \), if true when \( n=k \) then it must be true for \( n=k+1 \). Therefore it's true for all \( n \geq 1 \) by induction. \qed

Divisibility example

As an example of the latter case consider the theorem that \( 3^n + 7^n \) is always divisable by two.

1. Initial Step: Show it holds for \( n=1 \). \( 3^1 + 7^1 = 10 \) which is divisible by 2.
2. Construct a induction hypothesis. We assume that \( 3^k + 7^k \) is divisible by 2.

3. Perform the induction step: Prove the theorem when \( n = k+1 \). We want to show that \( 3^{k+1} + 7^{k+1} \) is divisible by 2.

   Consider

   \begin{align*} f(k+1) - 3f(k) &= 3^{k+1} + 7^{k+1} - 3(3^k + 7^k) \\

                &= 3(3^k) + 7(7^k) - 3(3^k) - 3(7^k) \\\\
                &= 4(7^k) \\\\
                &= 2 \times 2(7^k)

   \end{align*}

   \( f(k) \) is a multiple of 2, so \( 3f(k) \) is a multiple of 2. If \( f(k+1) - 3f(k) \) is a multiple of 2 then \( f(k+1) \) must be a multiple of 2 because only a multiple of 2 subtract another multiple of 2 gives a multiple 2. Therefore \(f(k+1)\) is divisible by 2.

4. Write a conclusion:

   We checked it's true when \( n=1 \), if true when \( n=k \) then it must be true for \( n=k+1 \). Therefore it's true for all \( n \geq 1 \) by induction. \qed