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

← Back to the worksheet

1. Answer to Question 1

   1. Left side \(1^3=1\); right side \(\tfrac14\times1\times4=1\). True for \(n=1\).
   2. Assume \(\displaystyle\sum_{r=1}^{k}r^3=\tfrac14k^2(k+1)^2\) for some positive integer \(k\).
   3. \(\displaystyle\sum_{r=1}^{k+1}r^3=\tfrac14k^2(k+1)^2+(k+1)^3=\tfrac14(k+1)^2\left(k^2+4(k+1)\right)=\tfrac14(k+1)^2(k+2)^2\), which is the formula with \(n=k+1\) ✓
   4. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   5. \(\tfrac14\times400\times441=\) 44 100

2. Answer to Question 2

   1. \(n=1\): left \(1\times2=2\), right \(\tfrac13\times1\times2\times3=2\) ✓
   2. Assume \(\displaystyle\sum_{r=1}^{k}r(r+1)=\tfrac13k(k+1)(k+2)\). Then \(\displaystyle\sum_{r=1}^{k+1}r(r+1)=\tfrac13k(k+1)(k+2)+(k+1)(k+2)=\tfrac13(k+1)(k+2)(k+3)\), the formula with \(n=k+1\) ✓
   3. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   4. \(\tfrac13(20)(21)(22)-\tfrac13(10)(11)(12)=3080-440=\) 2640

3. Answer to Question 3

   1. Let \(f(n)=5^n-1\). \(f(1)=4\) ✓. Assume \(f(k)=4m\). Then \(f(k+1)=5^{k+1}-1=5\cdot5^k-1=5(f(k)+1)-1=5f(k)+4=4(5m+1)\), divisible by 4. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   2. Let \(g(n)=3^{2n}-1=9^n-1\). \(g(1)=8\) ✓. Assume \(g(k)=8m\). Then \(g(k+1)=9\cdot9^k-1=9(g(k)+1)-1=9g(k)+8=8(9m+1)\), divisible by 8. True for all \(n\ge1\) by induction.
   3. \(3^{2n}=(3^2)^n=9^n\), so \(3^{2n}-1=9^n-1\). In (a) the key step was \(f(k+1)=5f(k)+4\), where 4 is \(5-1\); in (b) it was \(g(k+1)=9g(k)+8\), where 8 is \(9-1\). In general \(a^n-1\) is divisible by \(a-1\), by exactly the same argument.

4. Answer to Question 4

   1. \(f(k+1)=k^3+3k^2+3k+1+2k+2=k^3+3k^2+5k+3\), so \(f(k+1)-f(k)=3k^2+3k+3=\) \(3(k^2+k+1)\) ✓
   2. \(f(1)=3\) ✓. Assume \(f(k)=3m\). Then \(f(k+1)=f(k)+3(k^2+k+1)=3(m+k^2+k+1)\), a multiple of 3. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   3. \(f(10)=1000+20=1020=3\times340\) ✓

5. Answer to Question 5

   1. \(\mathbf A^2=\begin{pmatrix}4&0\\3&1\end{pmatrix}\), \(\mathbf A^3=\begin{pmatrix}8&0\\7&1\end{pmatrix}\)
   2. \(\mathbf A^n=\begin{pmatrix}2^n&0\\2^n-1&1\end{pmatrix}\)
   3. \(n=1\): \(\begin{pmatrix}2&0\\1&1\end{pmatrix}\) ✓. Assume \(\mathbf A^k=\begin{pmatrix}2^k&0\\2^k-1&1\end{pmatrix}\). Then \(\mathbf A^{k+1}=\mathbf A^k\mathbf A=\begin{pmatrix}2^k\cdot2&0\\2(2^k-1)+1&1\end{pmatrix}=\begin{pmatrix}2^{k+1}&0\\2^{k+1}-1&1\end{pmatrix}\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   4. \(\begin{pmatrix}1024&0\\1023&1\end{pmatrix}\)

6. Answer to Question 6

   1. \(u_2=8\), \(u_3=26\), \(u_4=80\)
   2. \(u_1=3-1=2\) ✓. Assume \(u_k=3^k-1\). Then \(u_{k+1}=3(3^k-1)+2=3^{k+1}-3+2=3^{k+1}-1\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   3. \(3^n-1>10^6\): \(3^{12}=531\,441\) and \(3^{13}=1\,594\,323\), so the first is \(u_{13}=1\,594\,322\).

7. Answer to Question 7

   1. \(T_4=10+10=\) 20
   2. \(n=1\): \(\tfrac16\times1\times2\times3=1\) ✓. Assume \(T_k=\tfrac16k(k+1)(k+2)\). Then \(T_{k+1}=T_k+\tfrac12(k+1)(k+2)=\tfrac16(k+1)(k+2)(k+3)\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   3. \(\tfrac16\times10\times11\times12=\) 220 cans
   4. \(T_{11}=286\) and \(T_{12}=364\), so 11 layers (using 286 cans).

8. Answer to Question 8

   1. \(u_2=50.50+50=\) £100.50; \(u_3=101.505+50=\) £151.51
   2. \(u_1=5000\times0.01=50\) ✓. Assume \(u_k=5000(1.01^k-1)\). Then \(u_{k+1}=1.01\times5000(1.01^k-1)+50=5000\times1.01^{k+1}-5050+50=5000(1.01^{k+1}-1)\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
   3. \(u_{24}=5000(1.01^{24}-1)=5000\times0.269735=\) £1348.67
   4. He paid in \(24\times50=£1200\), so the interest is £148.67.

9. Answer to Question 9

   1. When a new guest arrives, the \(n\) guests already there each shake hands with the new guest: \(n\) new handshakes.
   2. \(n=2\): \(h_2=1=\tfrac12\times2\times1\) ✓. Assume \(h_k=\tfrac12k(k-1)\). Then \(h_{k+1}=\tfrac12k(k-1)+k=\tfrac12k(k+1)=\tfrac12(k+1)k\) ✓. Since the result is true for \(n=2\) and the step holds, it is true for all \(n\ge2\) by induction.
   3. \(\tfrac12\times20\times19=\) 190
   4. \(n(n-1)=870\), \(n^2-n-870=0\), \((n-30)(n+29)=0\): 30 guests.

10. Answer to Question 10

    1. Move the top \(n\) discs to the spare peg (\(m_n\) moves), move the largest disc (1 move), then move the \(n\) discs on top of it (\(m_n\) moves): \(2m_n+1\) moves.
    2. \(m_1=2-1=1\) ✓. Assume \(m_k=2^k-1\). Then \(m_{k+1}=2(2^k-1)+1=2^{k+1}-1\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. \(2^{10}-1=\) 1023
    4. \(2^{20}-1=1\,048\,575\) s; dividing by \(86\,400\) s per day gives about 12.1 days.

11. Answer to Question 11

    1. The new cut crosses the \(k\) earlier cuts at \(k\) different points, which divide it into \(k+1\) segments. Each segment splits one piece into two, adding \(k+1\) pieces. (So \(R_4=7+4=11\).)
    2. \(R_1=\tfrac12(1+1+2)=2\) ✓. Assume \(R_k=\tfrac12(k^2+k+2)\). Then \(R_{k+1}=\tfrac12(k^2+k+2)+k+1=\tfrac12(k^2+3k+4)=\tfrac12\left((k+1)^2+(k+1)+2\right)\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. \(\tfrac12(64+8+2)=\) 37
    4. \(R_9=46\) and \(R_{10}=56\), so 10 cuts.

12. Answer to Question 12

    1. Both give £1.10 for each pound.
    2. \(n=1\): \(1+x\ge1+x\) ✓. Assume \((1+k x)\le(1+x)^k\). Since \(1+x\ge0\), multiply both sides by \(1+x\): \((1+x)^{k+1}\ge(1+x)(1+kx)=1+(k+1)x+kx^2\ge1+(k+1)x\), because \(kx^2\ge0\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. Take \(x=0.1\): \(1.1^n\ge1+0.1n\) for every \(n\), so compound interest gives at least as much.
    4. \(2000(1.1^{10})-2000(2)=5187.48-4000=\) £1187.48

13. Answer to Question 13

    1. \(4-1=3\), \(16-1=15\), \(64-1=63\): 1, 5 and 21 tiles.
    2. \(f(1)=3\) ✓. Assume \(4^k-1=3m\). Then \(4^{k+1}-1=4\cdot4^k-1=4(3m+1)-1=12m+3=3(4m+1)\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. \(\dfrac{4^5-1}3=\dfrac{1023}3=\) 341
    4. A count only shows that the area is right; the shape might still not fit. Split the \(2^{k+1}\) board into four \(2^k\) quarters. One quarter contains the fountain; place one L-tile at the centre covering one corner slab of each of the other three quarters. Now each quarter has exactly one slab missing, and by the inductive hypothesis each can be tiled.

14. Answer to Question 14

    1. \(s_3=48\), side length 3 cm.
    2. Every side becomes 4 sides, so \(s_{n+1}=4s_n\). \(s_1=3\times4^0=3\) ✓. Assume \(s_k=3\times4^{k-1}\); then \(s_{k+1}=4\times3\times4^{k-1}=3\times4^k\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. The side length at stage \(n\) is \(27\times\left(\tfrac13\right)^{n-1}\) (by a similar induction), so the perimeter is \(3\times4^{n-1}\times27\times3^{-(n-1)}=\) \(81\left(\tfrac43\right)^{n-1}\) ✓
    4. \(81\times\left(\tfrac43\right)^4=81\times\tfrac{256}{81}=\) 256 cm. Since \(\tfrac43>1\), the perimeter increases without limit, even though the snowflake stays inside a fixed circle.

15. Answer to Question 15

    1. \(f'(x)=(x+1)e^x\), \(f''(x)=(x+2)e^x\), \(f'''(x)=(x+3)e^x\)
    2. \(f^{(n)}(x)=(x+n)e^x\)
    3. \(n=1\): \(f'(x)=e^x+xe^x=(x+1)e^x\) ✓. Assume \(f^{(k)}(x)=(x+k)e^x\). Differentiate: \(f^{(k+1)}(x)=e^x+(x+k)e^x=(x+k+1)e^x\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    4. \(f^{(5)}(0)=(0+5)e^0=\) 5
    5. \(g'(x)=(1+2x)e^{2x}\), \(g''(x)=(4+4x)e^{2x}\): conjecture \(g^{(n)}(x)=2^{n-1}(2x+n)e^{2x}\). \(n=1\): \((2x+1)e^{2x}\) ✓. Assume true for \(k\); then \(g^{(k+1)}=2^{k-1}\left(2+2(2x+k)\right)e^{2x}=2^k(2x+k+1)e^{2x}\) ✓, so true for all \(n\).

16. Answer to Question 16

    1. \(F_7=13\), \(F_8=21\)
    2. \(n=1\): \(\mathbf Q=\begin{pmatrix}F_2&F_1\\F_1&F_0\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\) ✓. Assume true for \(k\). Then \(\mathbf Q^{k+1}=\begin{pmatrix}F_{k+1}&F_k\\F_k&F_{k-1}\end{pmatrix}\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}F_{k+1}+F_k&F_{k+1}\\F_k+F_{k-1}&F_k\end{pmatrix}=\begin{pmatrix}F_{k+2}&F_{k+1}\\F_{k+1}&F_k\end{pmatrix}\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. \(\det\mathbf Q=-1\), so \(\det(\mathbf Q^n)=(-1)^n\). But \(\det(\mathbf Q^n)=F_{n+1}F_{n-1}-F_n^2\), hence \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\) ✓
    4. \(F_7F_5-F_6^2=13\times5-64=65-64=1=(-1)^6\) ✓
    5. The top-right entry of \(\mathbf Q^{2n}\) is \(F_{2n}\). In \(\mathbf Q^n\mathbf Q^n\) it is \(F_{n+1}F_n+F_nF_{n-1}=\) \(F_n(F_{n+1}+F_{n-1})\) ✓

17. Answer to Question 17

    1. \(5!=120\), \(6!=720\); \(2^5=32\), \(2^6=64\). Smallest \(n\) is 4 (\(24>16\)).
    2. \(n=4\): \(24>16\) ✓. Assume \(k!>2^k\) for some \(k\ge4\). Then \((k+1)!=(k+1)k!>(k+1)2^k>2\times2^k=2^{k+1}\), since \(k+1>2\) ✓. Since true for \(n=4\) and true for \(k+1\) whenever true for \(k\ge4\), true for all \(n\ge4\) by induction.
    3. For \(n=1,2,3\) the statement is false (\(1<2\), \(2<4\), \(6<8\)), so the induction must start at the first value where it is true.
    4. \(n=4\): \(81>64\) ✓. Assume \(3^k>k^3\) for some \(k\ge4\). Then \(3^{k+1}=3\times3^k>3k^3>\left(1+\tfrac1k\right)^3k^3=(k+1)^3\) ✓. True for all \(n\ge4\).
    5. The first result shows that factorials eventually beat the exponential \(2^n\), so exponentials do not always win; the second shows that the exponential \(3^n\) beats the power \(n^3\). Each comparison needs its own proof and its own starting value.

18. Answer to Question 18

    1. First row: \(\tfrac34\), \(\tfrac45\). Second row: \(10+24=34\), \(34+64=98\).
    2. \(n=1\): \(\tfrac12=\tfrac12\) ✓. Assume the sum to \(k\) is \(\tfrac k{k+1}\). Then the sum to \(k+1\) is \(\dfrac k{k+1}+\dfrac1{(k+1)(k+2)}=\dfrac{k(k+2)+1}{(k+1)(k+2)}=\dfrac{(k+1)^2}{(k+1)(k+2)}=\dfrac{k+1}{k+2}\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    3. \(n=1\): \((0)2^2+2=2\) ✓. Assume the sum to \(k\) is \((k-1)2^{k+1}+2\). Adding \((k+1)2^{k+1}\) gives \(2k\cdot2^{k+1}+2=k\,2^{k+2}+2\), which is the formula with \(n=k+1\) ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    4. \(\dfrac n{n+1}>0.99\) gives \(n>0.99n+0.99\), \(0.01n>0.99\), \(n>99\): \(n=100\).
    5. \(\dfrac n{n+1}=1-\dfrac1{n+1}\), which tends to 1: the infinite series converges to 1.

19. Answer to Question 19

    1. \(f(1)=8+27=35=7\times5\), \(f(2)=16+243=259=7\times37\), \(f(3)=32+2187=2219=7\times317\).
    2. \(f(k+1)=2^{k+3}+3^{2k+3}=2\cdot2^{k+2}+9\cdot3^{2k+1}=2\left(2^{k+2}+3^{2k+1}\right)+7\cdot3^{2k+1}=\) \(2f(k)+7\times3^{2k+1}\) ✓
    3. \(f(1)=35\) ✓. Assume \(f(k)=7m\). Then \(f(k+1)=14m+7\times3^{2k+1}=7(2m+3^{2k+1})\), divisible by 7 ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    4. \(f(k+1)-9f(k)=2\cdot2^{k+2}-9\cdot2^{k+2}=\) \(-7\times2^{k+2}\), also a multiple of 7, so \(f(k+1)=9f(k)-7\times2^{k+2}\) gives an equally good proof.

20. Answer to Question 20

    1. \(n=1\) is clear. Assume \((\cos\theta+i\sin\theta)^k=\cos k\theta+i\sin k\theta\). Then \((\cos\theta+i\sin\theta)^{k+1}=(\cos k\theta+i\sin k\theta)(\cos\theta+i\sin\theta)=(\cos k\theta\cos\theta-\sin k\theta\sin\theta)+i(\sin k\theta\cos\theta+\cos k\theta\sin\theta)=\cos(k+1)\theta+i\sin(k+1)\theta\) by the addition formulae ✓. Since the result is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\), by mathematical induction it is true for all positive integers \(n\).
    2. \((\cos\theta+i\sin\theta)(\cos\theta-i\sin\theta)=\cos^2\theta+\sin^2\theta=1\), so the inverse is \(\cos\theta-i\sin\theta=\cos(-\theta)+i\sin(-\theta)\) ✓
    3. Let \(n=-m\) with \(m\) a positive integer. \((\cos\theta+i\sin\theta)^{-m}=\left((\cos\theta+i\sin\theta)^{-1}\right)^m=\left(\cos(-\theta)+i\sin(-\theta)\right)^m=\cos(-m\theta)+i\sin(-m\theta)\) by part (a), which is \(\cos n\theta+i\sin n\theta\) ✓
    4. \(1+i=\sqrt2\left(\cos\tfrac\pi4+i\sin\tfrac\pi4\right)\), so \((1+i)^8=16(\cos2\pi+i\sin2\pi)=\) 16. Check: \((1+i)^2=2i\), so \((1+i)^8=(2i)^4=16i^4=16\) ✓