Proof by induction – further maths revision notes to download as PDF

Example 1

Prove that \(\sum_{r=1}^{n}r^2=\tfrac16 n(n+1)(2n+1)\).

Basis \(n=1\): LHS \(=1\), RHS \(=\tfrac16\cdot1\cdot2\cdot3=1\). True.

Assume true for \(n=k\): \(\sum_{r=1}^{k}r^2=\tfrac16k(k+1)(2k+1)\).

Then \(\sum_{r=1}^{k+1}r^2=\tfrac16k(k+1)(2k+1)+(k+1)^2=\tfrac16(k+1)\left[k(2k+1)+6(k+1)\right]=\tfrac16(k+1)(2k^2+7k+6)=\tfrac16(k+1)(k+2)(2k+3)\), which is the formula with \(n=k+1\). So true for \(n=k+1\); with the basis, true for all \(n\ge1\).

Example 2

Prove that \(f(n)=7^n+5\) is divisible by 6 for \(n\ge1\).

\(f(1)=12=6\times2\). Assume \(f(k)=6m\). Then \(f(k+1)-f(k)=7^{k+1}-7^k=6\cdot7^k\), so \(f(k+1)=6m+6\cdot 7^k=6(m+7^k)\), which is divisible by 6. Hence true for all \(n\ge1\).

Example 3

Prove that \(\begin{pmatrix}1&2\\0&1\end{pmatrix}^n=\begin{pmatrix}1&2n\\0&1\end{pmatrix}\).

Basis \(n=1\) is immediate. If true for \(k\), then \(\begin{pmatrix}1&2k\\0&1\end{pmatrix}\begin{pmatrix}1&2\\0&1\end{pmatrix}=\begin{pmatrix}1&2+2k\\0&1\end{pmatrix}=\begin{pmatrix}1&2(k+1)\\0&1\end{pmatrix}\). Done.

Example 4: recurrence

Given \(u_1=4\) and \(u_{n+1}=2u_n-3\), prove that \(u_n=2^{n-1}+3\).

Basis: \(2^0+3=4\). Assume \(u_k=2^{k-1}+3\). Then \(u_{k+1}=2(2^{k-1}+3)-3=2^k+3\), the formula with \(n=k+1\). The conjecture came from calculating \(u_2=5,\ u_3=7,\ u_4=11\): the differences from 3 are \(1,2,4,8\), a doubling pattern.

Example 5: inequality

Prove that \(2^n\ge n+1\) for \(n\ge1\).

Basis \(n=1\): \(2\ge2\). Assume \(2^k\ge k+1\). Then \(2^{k+1}=2\times2^k\ge2(k+1)=2k+2\ge k+2\) since \(k\ge0\). So true for \(n=k+1\).

Worked example 6: the sum of odd numbers

Prove that \(\sum_{r=1}^{n}(2r-1)=n^2\).

For \(n=1\) the left side is \(1\) and the right side is \(1^2=1\), so the statement is true. Assume that \(\sum_{r=1}^{k}(2r-1)=k^2\). Adding the next term, which is \(2(k+1)-1=2k+1\), gives \(\sum_{r=1}^{k+1}(2r-1)=k^2+2k+1=(k+1)^2\). This is the statement with \(n=k+1\). Since the statement is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), it is true for all positive integers by induction. A picture explains the result: each odd number is an L-shaped border that turns a square of side \(k\) into a square of side \(k+1\).

Worked example 7: divisibility using a difference

Prove that \(8^n-3^n\) is divisible by 5 for all positive integers \(n\).

Let \(f(n)=8^n-3^n\). Then \(f(1)=5\), which is divisible by 5. Assume that \(f(k)=5m\) for some integer \(m\). Then \(f(k+1)=8\cdot8^k-3\cdot3^k=8(8^k-3^k)+8\cdot3^k-3\cdot3^k=8f(k)+5\cdot3^k\). Both terms are multiples of 5, so \(f(k+1)\) is divisible by 5. The key idea is to split off a multiple of \(f(k)\) and check that what remains is a multiple of the divisor. Another way is to work out \(f(k+1)-8f(k)\) directly, which gives the same result.

Worked example 8: a sequence defined by a recurrence

Given that \(u_1=1\) and \(u_{n+1}=u_n+2n+1\), prove that \(u_n=n^2\).

For \(n=1\) the formula gives \(1^2=1=u_1\). Assume that \(u_k=k^2\). Then \(u_{k+1}=k^2+2k+1=(k+1)^2\), so the formula is true for \(n=k+1\). By induction, \(u_n=n^2\) for all positive integers \(n\). Notice that the recurrence relation provides the link between consecutive terms, so the inductive step is often just one line of algebra. The work is in guessing the formula, which can be done by calculating the first few terms.