Proof by Induction (DP IB Analysis & Approaches (AA): HL): Revision Note

Proof by induction

What is proof by induction?

• Proof by induction is a way of proving a result is true for a set of integers

  • by showing that if it is true for one integer

    • then it is true for the next integer

• It can be thought of as falling dominoes

  • Assuming some domino falls

    • the assumption step

  • you need to show it causes (induces) the next domino to fall

    • the induction step

  • If you can also show that the first domino falls

    • the basic step

  • then putting together the above mean that all dominoes will fall!

    • the conclusion step

What are the steps for proof by induction with series?

• For example: prove that $\sum _{r=1}^n{r}^2=\frac{1}{6}n(n+1)(2n+1)$ for all $n\in {\mathrm{\mathbb{Z}}}^{+}$

  • It has a left-hand side, $LHS=\sum _{r=1}^n{r}^2$

  • and a right-hand side, $RHS=\frac{1}{6}n(n+1)(2n+1)$

• STEP 1

  The basic step: Show result is true for $\mathit{n}\mathbf{=}\mathbf{1}$

  • Substitute $n=1$ into both sides individually and show they are equal

    $\begin{array}{l}LHS=\sum _{r=1}^1{r}^2=1^2=1\\ RHS=\frac{1}{6}\times 1\times (1+1)(2\times 1+1)=\frac{1}{6}\times 2\times 3=1\end{array}$

• STEP 2

  The assumption step: Assume the LHS and RHS are equal for some $\mathit{n}\mathbf{=}\mathit{k}$ (where $k$ is some integer)

  • Replace $n$ with $k$ in the statement

  • Write: "Assume $\sum _{r=1}^k{r}^2=\frac{1}{6}k(k+1)(2k+1)$ is true"

• STEP 3

  The inductive step: You need to prove that the LHS and RHS are equal for $n=k+1$

  • Start with the LHS for $n=k+1$

    • It helps to take the last term out: $\sum _{r=1}^{k+1}{r}^2=\sum _{r=1}^k{r}^2+{\left(k+1\right)}^2$

    • Now substitute in the assumption (from step 2) :

    • $\sum _{r=1}^{k+1}{r}^2=\frac{1}{6}k(k+1)(2k+1)+{\left(k+1\right)}^2$

    • Expand and factorise:
      $\begin{array}{l}\frac{1}{6}\left(k+1\right)[k(2k+1)+6\left(k+1\right)]\\ =\frac{1}{6}\left(k+1\right)[2k^2+7k+6]\\ =\frac{1}{6}\left(k+1\right)\left(k+2\right)\left(2k+3\right)\end{array}$

  • Check if it is the same as the RHS for $n=k+1$

    $\begin{array}{rcl}RHS& =& \frac{1}{6}\left(k+1\right)\left(\left(k+1\right)+1\right)\left(2\left(k+1\right)+1\right)\\ & =& \frac{1}{6}\left(k+1\right)\left(k+2\right)\left(2k+3\right)\end{array}$

  • So LHS = RHS for $n=k+1$ (as long as the assumption is true)

• STEP 4

  The conclusion step: Explain in words how the above steps make the result true for all positive integers, $n\in {\mathrm{\mathbb{Z}}}^{+}$, using the following two sentences:

  • "If it is true for $n=k$, then it is true for $n=k+1$."

  • "As it is true for $\mathit{n}\mathbf{=}\mathbf{1}$, the statement is true for all $n\in {\mathrm{\mathbb{Z}}}^{+}$."

What are the steps for proof by induction with divisibility?

• For example: prove that $f\left(n\right)=4^n-1$ is divisible by 3 for all positive integers $n$

  • Being divisible by 3 is the same as being a multiple of 3

• STEP 1

  The basic step: Show result is true for $\mathit{n}\mathbf{=}\mathbf{1}$

  • Substitute $n=1$ into the function

  • $f\left(1\right)=4^1-1=3$which is divisible by 3

• STEP 2

  The assumption step: Assume $f\left(k\right)=4^k-1$ is divisible by 3 for some $\mathit{n}\mathbf{=}\mathit{k}$ where $k$ is some integer

  • Replace $n$ with $k$ in the statement

  • Write "divisible by 3" as "$=3m$" where $m$ is a positive integer

  • So$f\left(k\right)=4^k-1=3m$ where $m\in {\mathrm{\mathbb{Z}}}^{+}$ 

  • It helps to make $4^k$ the subject: $4^k=1+3m$ 

• STEP 3

  The inductive step (method 1): You need to show that the $n=k+1$ case is divisible by 3

  • Substitute $n=k+1$ into the function

    • $f(k+1)=4^{k+1}-1$

  • Use index laws to substitute in the assumption (step 2) $4^k=1+3m$ 

    • $f(k+1)=4\left(4^k\right)-1=4\left(1+3m\right)-1=3\left(4m+1\right)$which is a multiple of 3

  • So $f(k+1)$is divisible by 3 (as long as the assumption is true)

• STEP 3

  The inductive step (method 2): An alternative method is to show that the difference $f(k+1)-f\left(k\right)$ is a multiple of 3

  • This is because $f(k+1)-f\left(k\right)=3\times ...$ rearranges to $f(k+1)=f\left(k\right)+3\times ...$

  • So $f(k+1)$ is divisible by 3 (as long as the assumption is true, i.e. that $f\left(k\right)$ is divisible by 3)

  • This method is not always that practical

    • When it is, a hint will be given

• STEP 4

  The conclusion step: Explain in words how the above steps make the result true for all integers, using the following two sentences:

  • "If it is true for $n=k$, then it is true for $n=k+1$."

  • "As it is true for $\mathit{n}\mathbf{=}\mathbf{1}$, the statement is true for all $n\in {\mathrm{\mathbb{Z}}}^{+}$."

What types of statements might I be asked to prove by induction?

• You may be asked to use proof by induction in the following contexts

  • Series (see above)

    • Some useful tricks are

      • writing $\sum _{r=1}^{k+1}f\left(r\right)=f\left(k+1\right)+\sum _{r=1}^{k}f\left(r\right)$ for the inductive step

      • writing $\left(k+1\right)!=\left(k+1\right)\times \left(k!\right)$ if factorials are involved

  • Divisibility (see above)

    • A useful trick for the inductive step is using $a^{k+1}=a\times a^k$

  • Complex numbers

    • You can prove de Moivre’s theorem by induction

  • Derivatives

    • These may involve the chain, product and quotient rule

    • A useful trick for the inductive step is using $f^{\left(k+1\right)}\left(x\right)=\frac{d}{dx}\left(f^{\left(k\right)}\left(x\right)\right)$