FP1 June 2011 Q9
9. Prove by induction, that for \(n \in \mathbb{Z}^+\),
(a) \[\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}^n = \begin{pmatrix} 3^n & 0 \\ 3(3^n - 1) & 1 \end{pmatrix},\] (6)
(b) \(\mathrm{f}(n) = 7^{2n-1} + 5\) is divisible by 12. (6)
| Scheme | Marks |
|---|---|
| \(n = 1;\quad \text{LHS} = \begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}^1 = \begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}\) \(\text{RHS} = \begin{pmatrix} 3^1 & 0 \\ 3(3^1 - 1) & 1 \end{pmatrix} = \begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}\) As LHS = RHS, the matrix result is true for \(n = 1\). Check to see that the result is true for \(n = 1\). | B1 |
| Assume that the matrix equation is true for \(n = k\), ie. \(\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}^k = \begin{pmatrix} 3^k & 0 \\ 3(3^k - 1) & 1 \end{pmatrix}\) | |
| With \(n = k + 1\) the matrix equation becomes \(\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}^{k+1} = \begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}^k\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}\) | |
| \(= \begin{pmatrix} 3^k & 0 \\ 3(3^k - 1) & 1 \end{pmatrix}\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}\) or \(\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}\begin{pmatrix} 3^k & 0 \\ 3(3^k - 1) & 1 \end{pmatrix}\) \(\begin{pmatrix} 3^k & 0 \\ 3(3^k - 1) & 1 \end{pmatrix}\) by \(\begin{pmatrix} 3 & 0 \\ 6 & 1 \end{pmatrix}\) | M1 |
| \(= \begin{pmatrix} 3^{k+1} + 0 & 0 + 0 \\ 9(3^k - 1) + 6 & 0 + 1 \end{pmatrix}\) or \(\begin{pmatrix} 3^{k+1} + 0 & 0 + 0 \\ 6.3^k + 3(3^k - 1) & 0 + 1 \end{pmatrix}\) Correct unsimplified matrix with no errors seen. | A1 |
| \(= \begin{pmatrix} 3^{k+1} & 0 \\ 9(3^k) - 3 & 1 \end{pmatrix}\) | |
| \(= \begin{pmatrix} 3^{k+1} & 0 \\ 3\left(3(3^k) - 1\right) & 1 \end{pmatrix}\) | |
| \(= \begin{pmatrix} 3^{k+1} & 0 \\ 3(3^{k+1} - 1) & 1 \end{pmatrix}\) Manipulates so that \(k \to k + 1\) on at least one term. Correct result with no errors seen with some working between this and the previous A1 | dM1 A1 |
| If the result is true for \(n = k\), (1) then it is now true for \(n = k + 1\). (2) As the result has shown to be true for \(n = 1\), (3) then the result is true for all \(n\). (4) All 4 aspects need to be mentioned at some point for the last A1. Correct conclusion with all previous marks earned | A1 cso |
| (6) |
| Scheme | Marks |
|---|---|
| \(\mathrm{f}(1) = 7^{2-1} + 5 = 7 + 5 = 12\), Shows that \(\mathrm{f}(1) = 12\). | B1 |
| {which is divisible by 12}. \(\{\therefore \mathrm{f}(n)\) is divisible by 12 when \(n = 1.\}\) | |
| Assume that for \(n = k\), \(\mathrm{f}(k) = 7^{2k-1} + 5\) is divisible by 12 for \(k \in \mathbb{Z}^+\). | |
| So, \(\mathrm{f}(k + 1) = 7^{2(k+1)-1} + 5\) Correct unsimplified expression for \(\mathrm{f}(k + 1)\). | B1 |
| giving, \(\mathrm{f}(k + 1) = 7^{2k+1} + 5\) | |
| \(\therefore \mathrm{f}(k + 1) - \mathrm{f}(k) = \left(7^{2k+1} + 5\right) - \left(7^{2k-1} + 5\right)\) Applies \(\mathrm{f}(k + 1) - \mathrm{f}(k)\). No simplification is necessary and condone missing brackets. | M1 |
| \(= 7^{2k+1} - 7^{2k-1}\) | |
| \(= 7^{2k-1}\left(7^2 - 1\right)\) Attempting to isolate \(7^{2k-1}\) | M1 |
| \(= 48\left(7^{2k-1}\right)\) \(48\left(7^{2k-1}\right)\) | A1cso |
| \(\therefore \mathrm{f}(k + 1) = \mathrm{f}(k) + 48\left(7^{2k-1}\right)\), which is divisible by 12 as both \(\mathrm{f}(k)\) and \(48\left(7^{2k-1}\right)\) are both divisible by 12. (1) If the result is true for \(n = k\), (2) then it is now true for \(n = k + 1\). (3) As the result has shown to be true for \(n = 1\), (4) then the result is true for all \(n\). (5). All 5 aspects need to be mentioned at some point for the last A1. Correct conclusion with no incorrect work. Don’t condone missing brackets. | A1 cso |
| (6) | |
| (12 marks) |
Notes
There are other ways of proving this by induction. See appendix for 3 alternatives.
If you are in any doubt consult your team leader and/or use the review system.
Alternative (Way 2)
| Scheme | Marks |
|---|---|
| \(\mathrm{f}(1) = 7^{2-1} + 5 = 7 + 5 = 12\), Shows that \(\mathrm{f}(1) = 12\). | B1 |
| {which is divisible by 12}. \(\{\therefore \mathrm{f}(n)\) is divisible by 12 when \(n = 1.\}\) | |
| Assume that for \(n = k\), \(\mathrm{f}(k) = 7^{2k-1} + 5\) is divisible by 12 for \(k \in \mathbb{Z}^+\). | |
| So, \(\mathrm{f}(k + 1) = 7^{2(k+1)-1} + 5\) Correct expression for \(\mathrm{f}(k + 1)\). | B1 |
| giving, \(\mathrm{f}(k + 1) = 7^{2k+1} + 5\) | |
| \(7^{2k+1} + 5 = 49 \times 7^{2k-1} + 5\) Attempt to isolate \(7^{2k-1}\) | M1 |
| \(= 49 \times \left(7^{2k-1} + 5\right) - 240\) M1 Attempt to isolate \(7^{2k-1} + 5\) | M1 |
| \(\mathrm{f}(k + 1) = 49 \times \mathrm{f}(k) - 240\) Correct expression in terms of \(\mathrm{f}(k)\) | A1 |
| As both \(\mathrm{f}(k)\) and 240 are divisible by 12 then so is \(\mathrm{f}(k + 1)\). If the result is true for \(n = k\), then it is now true for \(n = k + 1\). As the result has shown to be true for \(n = 1\), then the result is true for all \(n\). Correct conclusion | A1 |
| (6) |
Alternative (Way 3)
| Scheme | Marks |
|---|---|
| \(\mathrm{f}(1) = 7^{2-1} + 5 = 7 + 5 = 12\), Shows that \(\mathrm{f}(1) = 12\). | B1 |
| {which is divisible by 12}. \(\{\therefore \mathrm{f}(n)\) is divisible by 12 when \(n = 1.\}\) | |
| Assume that for \(n = k\), \(\mathrm{f}(k)\) is divisible by 12 so \(\mathrm{f}(k) = 7^{2k-1} + 5 = 12m\) | |
| So, \(\mathrm{f}(k + 1) = 7^{2(k+1)-1} + 5\) Correct expression for \(\mathrm{f}(k + 1)\). | B1 |
| giving, \(\mathrm{f}(k + 1) = 7^{2k+1} + 5\) | |
| \(7^{2k+1} + 5 = 7^2.7^{2k-1} + 5 = 49 \times 7^{2k-1} + 5\) Attempt to isolate \(7^{2k-1}\) | M1 |
| \(= 49 \times (12m - 5) + 5\) Substitute for \(m\) | M1 |
| \(\mathrm{f}(k + 1) = 49 \times 12m - 240\) Correct expression in terms of \(m\) | A1 |
| As both \(49 \times 12m\) and 240 are divisible by 12 then so is \(\mathrm{f}(k + 1)\). If the result is true for \(n = k\), then it is now true for \(n = k + 1\). As the result has shown to be true for \(n = 1\), then the result is true for all \(n\). Correct conclusion | A1 |
| (6) |
Alternative (Way 4)
| Scheme | Marks |
|---|---|
| \(\mathrm{f}(1) = 7^{2-1} + 5 = 7 + 5 = 12\), Shows that \(\mathrm{f}(1) = 12\). | B1 |
| {which is divisible by 12}. \(\{\therefore \mathrm{f}(n)\) is divisible by 12 when \(n = 1.\}\) | |
| Assume that for \(n = k\), \(\mathrm{f}(k) = 7^{2k-1} + 5\) is divisible by 12 for \(k \in \mathbb{Z}^+\). | |
| \(\mathrm{f}(k + 1) + 35\mathrm{f}(k) = \underline{7^{2(k+1)-1} + 5} + 35(7^{2k-1} + 5)\) Correct expression for \(\mathrm{f}(k + 1)\). | B1 |
| \(\mathrm{f}(k + 1) + 35\mathrm{f}(k) = 7^{2k+1} + 5 + 35(7^{2k-1} + 5)\) Add appropriate multiple of \(\mathrm{f}(k)\) For \(7^{2k}\) this is likely to be 35 (119, 203,.) For \(7^{2k-1}\) 11 (23, 35, 47,..) | M1 |
| giving, \(7.7^{2k} + 5 + 5.7^{2k} + 175\) Attempt to isolate \(7^{2k}\) | M1 |
| \(= 180 + 12 \times 7^{2k} = 12\left(15 + 7^{2k}\right)\) Correct expression | A1 |
| \(\therefore \mathrm{f}(k + 1) = 12\left(7^{2k} + 15\right) - 35\mathrm{f}(k)\). As both \(\mathrm{f}(k)\) and \(12\left(7^{2k} + 15\right)\) are divisible by 12 then so is \(\mathrm{f}(k + 1)\). If the result is true for \(n = k\), then it is now true for \(n = k + 1\). As the result has shown to be true for \(n = 1\), then the result is true for all \(n\). Correct conclusion | A1 |
| (6) |