Proof by induction – further maths worksheet with answers to download as PDF

Prove by induction that, for all positive integers \(n\), \(\displaystyle\sum_{r=1}^{n}r^3=\tfrac14n^2(n+1)^2\).

1. Show that the result is true for \(n=1\).
2. Write down the assumption for \(n=k\).
3. Show that the result is true for \(n=k+1\).
4. Write a conclusion.
5. Use the result to find \(1^3+2^3+\cdots+20^3\).

Prove by induction that \(\displaystyle\sum_{r=1}^{n}r(r+1)=\tfrac13n(n+1)(n+2)\) for all \(n\in\mathbb Z^+\).

1. Prove the basis case.
2. Carry out the inductive step, showing your algebra clearly.
3. State the conclusion.
4. Hence evaluate \(\displaystyle\sum_{r=11}^{20}r(r+1)\).

Use induction to prove each statement for all positive integers \(n\).

1. \(5^n-1\) is divisible by 4.
2. \(3^{2n}-1\) is divisible by 8.
3. Write \(3^{2n}-1\) as a power of 9 minus 1, and explain how the proof in part (b) is the same method as the proof in part (a) with 5 replaced by 9.

Let \(f(n)=n^3+2n\).

1. Show that \(f(k+1)-f(k)=3(k^2+k+1)\).
2. Hence prove by induction that \(f(n)\) is divisible by 3 for all positive integers \(n\).
3. Check your result for \(n=10\).

Let \(\mathbf A=\begin{pmatrix}2&0\\1&1\end{pmatrix}\).

1. Find \(\mathbf A^2\) and \(\mathbf A^3\).
2. Suggest a formula for \(\mathbf A^n\).
3. Prove your formula by induction.
4. Hence find \(\mathbf A^{10}\).

A sequence is defined by \(u_1=2\) and \(u_{n+1}=3u_n+2\).

1. Find \(u_2\), \(u_3\) and \(u_4\).
2. Prove by induction that \(u_n=3^n-1\).
3. Find the first term of the sequence that exceeds one million.

A supermarket builds a pyramid of cans with triangular layers. The top layer has 1 can, the next has 3, then 6, and in general layer \(r\) (counting from the top) has \(\tfrac12r(r+1)\) cans.

1. Complete the table.
2. Prove by induction that \(T_n=\tfrac16n(n+1)(n+2)\).
3. Find the number of cans in a pyramid with 10 layers.
4. The manager has 300 cans. Find the greatest number of complete layers she can build.

Ali saves £50 at the end of every month in an account that pays 1% interest per month. His balance after \(n\) months is \(u_n\), where \(u_1=50\) and \(u_{n+1}=1.01u_n+50\).

1. Find \(u_2\) and \(u_3\).
2. Prove by induction that \(u_n=5000(1.01^n-1)\).
3. Find his balance after two years.
4. How much of this balance is interest?

At a party every guest shakes hands once with every other guest. Let \(h_n\) be the number of handshakes when there are \(n\) guests.

1. Explain why \(h_{n+1}=h_n+n\).
2. Prove by induction that \(h_n=\tfrac12n(n-1)\) for all \(n\ge2\).
3. Find the number of handshakes when 20 guests are present.
4. How many guests were present if there were 435 handshakes?

In the Tower of Hanoi puzzle, \(n\) discs of different sizes must be moved from one peg to another, one at a time, never placing a larger disc on a smaller one. The least number of moves \(m_n\) satisfies \(m_1=1\) and \(m_{n+1}=2m_n+1\).

1. Explain the recurrence relation: how can \(n+1\) discs be moved using the solution for \(n\) discs?
2. Prove by induction that \(m_n=2^n-1\).
3. Find the least number of moves for 10 discs.
4. A machine makes one move per second. How many days does it take to move 20 discs?

A pizza is cut with \(n\) straight cuts, each crossing every other cut, with no three cuts meeting at a point. The greatest number of pieces is \(R_n\).

1. Explain why the \((k+1)\)th cut adds \(k+1\) new pieces.
2. Prove by induction that \(R_n=\tfrac12(n^2+n+2)\).
3. Find the greatest number of pieces with 8 cuts.
4. Find the least number of cuts needed for at least 50 pieces.

A bank offers 10% interest per year. With compound interest £1 grows to \(1.1^n\) pounds after \(n\) years; with simple interest it grows to \(1+0.1n\) pounds.

1. Show that both give the same amount after 1 year.
2. Prove by induction that \((1+x)^n\ge1+nx\) for all positive integers \(n\) and all \(x\ge-1\) (Bernoulli's inequality).
3. Deduce that compound interest is never worse than simple interest at the same rate.
4. Find the difference between the two amounts for £2000 after 10 years.

A square courtyard of \(2^n\) by \(2^n\) slabs has one slab removed for a fountain. A builder covers the remaining \(4^n-1\) slabs with L-shaped tiles, each covering exactly 3 slabs.

1. Show that the number of slabs to be covered is a whole number of L-tiles when \(n=1\), \(2\) and \(3\).
2. Prove by induction that \(4^n-1\) is divisible by 3 for all \(n\ge1\).
3. Find the number of L-tiles needed when \(n=5\).
4. Explain why divisibility alone does not prove that the tiling is possible, and describe how the board can be split into four quarters to build a full proof.

A Koch snowflake starts as an equilateral triangle of side 27 cm (stage 1). At each stage the middle third of every side is replaced by two sides of an equilateral bump, so each side becomes 4 sides that are one third as long.

1. Complete the table.
2. Explain why \(s_{n+1}=4s_n\), and prove by induction that \(s_n=3\times4^{n-1}\).
3. Show that the perimeter at stage \(n\) is \(81\left(\tfrac43\right)^{n-1}\) cm.
4. Find the perimeter at stage 5, and explain what happens to the perimeter as \(n\) increases.

Let \(f(x)=xe^x\), and write \(f^{(n)}(x)\) for the \(n\)th derivative.

1. Complete the table.
2. Suggest a formula for \(f^{(n)}(x)\).
3. Prove your formula by induction.
4. Find \(f^{(5)}(0)\).
5. Use a similar method to find and prove a formula for the \(n\)th derivative of \(g(x)=xe^{2x}\).

The Fibonacci numbers are \(F_0=0\), \(F_1=1\) and \(F_{n+1}=F_n+F_{n-1}\). Let \(\mathbf Q=\begin{pmatrix}1&1\\1&0\end{pmatrix}\).

1. Complete the table.
2. Prove by induction that \(\mathbf Q^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\) for \(n\ge1\).
3. By taking determinants, prove Cassini's identity \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\).
4. Check Cassini's identity for \(n=6\).
5. Use \(\mathbf Q^{2n}=\mathbf Q^n\mathbf Q^n\) to show that \(F_{2n}=F_n(F_{n+1}+F_{n-1})\).

The table compares \(n!\) with \(2^n\) for small values of \(n\).

1. Complete the table, and state the smallest value of \(n\) for which \(n!>2^n\).
2. Prove by induction that \(n!>2^n\) for all integers \(n\ge4\).
3. Explain why the basis case must be \(n=4\) and not \(n=1\).
4. Prove by induction that \(3^n>n^3\) for all integers \(n\ge4\). (You may use the fact that \(\left(1+\tfrac1n\right)^3\le\left(\tfrac54\right)^3<3\) for \(n\ge4\).)
5. A student says that both inequalities show "exponentials always win". Comment on the two results.

A student uses a spreadsheet to add up two series and notices patterns in the totals.

1. Complete the table.
2. Prove by induction that \(\displaystyle\sum_{r=1}^{n}\frac1{r(r+1)}=\frac n{n+1}\).
3. Prove by induction that \(\displaystyle\sum_{r=1}^{n}r\,2^r=(n-1)2^{n+1}+2\).
4. Find the smallest \(n\) for which the first sum exceeds 0.99.
5. Explain what happens to the first sum as \(n\) becomes very large.

Let \(f(n)=2^{n+2}+3^{2n+1}\).

1. Complete the table and show that each value is divisible by 7.
2. Show that \(f(k+1)=2f(k)+7\times3^{2k+1}\).
3. Hence prove by induction that \(f(n)\) is divisible by 7 for all \(n\ge1\).
4. Explain why it would also be valid to consider \(f(k+1)-9f(k)\), and find this expression.

De Moivre's theorem states that \((\cos\theta+i\sin\theta)^n=\cos n\theta+i\sin n\theta\).

1. Prove the theorem by induction for all positive integers \(n\).
2. Show that \((\cos\theta+i\sin\theta)^{-1}=\cos\theta-i\sin\theta\).
3. Hence prove the theorem for all negative integers \(n\).
4. Use the theorem to find \((1+i)^{8}\) and check by expanding \((1+i)^2\).