FP1 June 2012 Q10

EdexcelOld spec6 marksInduction

10. Prove by induction that, for \(n \in \mathbb{Z}^+\), \[\mathrm{f}(n) = 2^{2n-1} + 3^{2n-1} \text{ is divisible by 5.}\] (6)

Mark scheme

Scheme	Marks
\(\mathrm{f}(n) = 2^{2n-1} + 3^{2n-1}\) is divisible by 5.
\(\mathrm{f}(1) = 2^1 + 3^1 = 5\), Shows that \(\mathrm{f}(1) = 5\).	B1
Assume that for \(n = k\), \(\mathrm{f}(k) = 2^{2k-1} + 3^{2k-1}\) is divisible by 5 for \(k \in \mathbb{Z}^+\).
\(\mathrm{f}(k + 1) - \mathrm{f}(k) = 2^{2(k+1)-1} + 3^{2(k+1)-1} - \left(2^{2k-1} + 3^{2k-1}\right)\) M1: Attempts \(\mathrm{f}(k + 1) - \mathrm{f}(k)\). A1: Correct expression for \(\mathrm{f}(k + 1)\) (Can be unsimplified)	M1A1
\(= 2^{2k+1} + 3^{2k+1} - 2^{2k-1} - 3^{2k-1}\)
\(= 2^{2k-1+2} + 3^{2k-1+2} - 2^{2k-1} - 3^{2k-1}\)
\(= 4\left(2^{2k-1}\right) + 9\left(3^{2k-1}\right) - 2^{2k-1} - 3^{2k-1}\) Achieves an expression in \(2^{2k-1}\) and \(3^{2k-1}\)	M1
\(= 3\left(2^{2k-1}\right) + 8\left(3^{2k-1}\right)\)
\(= 3\left(2^{2k-1}\right) + 3\left(3^{2k-1}\right) + 5\left(3^{2k-1}\right)\)
\(= 3\mathrm{f}(k) + 5\left(3^{2k-1}\right)\)
\(\therefore \mathrm{f}(k + 1) = 4\mathrm{f}(k) + 5\left(3^{2k-1}\right)\) or \(4\left(2^{2k-1} + 3^{2k-1}\right) + 5\left(3^{2k-1}\right)\) Where \(\mathrm{f}(k + 1)\) is correct and is clearly a multiple of 5.	A1
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 at the end, at least as given, and all previous marks scored.	A1 cso
	[6]
	6 marks

Notes

All methods should complete to \(\mathrm{f}(k + 1) = \ldots\) where \(\mathrm{f}(k + 1)\) is clearly shown to be divisible by 5 to enable the final 2 marks to be available.

Note that there are many different ways of proving this result by induction.

Alternative (Way 2)

Scheme	Marks
\(\mathrm{f}(n) = 2^{2n-1} + 3^{2n-1}\) is divisible by 5.
\(\mathrm{f}(1) = 2^1 + 3^1 = 5\) Shows that \(\mathrm{f}(1) = 5\).	B1
Assume that for \(n = k\), \(\mathrm{f}(k) = 2^{2k-1} + 3^{2k-1}\) is divisible by 5 for \(k \in \mathbb{Z}^+\).
\(\mathrm{f}(k + 1) = 2^{2(k+1)-1} + 3^{2(k+1)-1}\) M1: Attempts \(\mathrm{f}(k + 1)\). A1: Correct expression for \(\mathrm{f}(k + 1)\) (Can be unsimplified)	M1A1
\(= 2^{2k+1} + 3^{2k+1}\)
\(= 4\left(2^{2k-1}\right) + 9\left(3^{2k-1}\right)\) Achieves an expression in \(2^{2k-1}\) and \(3^{2k-1}\)	M1
\(\mathrm{f}(k + 1) = 4\left(2^{2k-1} + 3^{2k-1}\right) + 5\left(3^{2k-1}\right)\) or \(\mathrm{f}(k + 1) = 4\mathrm{f}(k) + 5\left(3^{2k-1}\right)\) or \(\mathrm{f}(k + 1) = 9\mathrm{f}(k) - 5\left(2^{2k-1}\right)\) or \(\mathrm{f}(k + 1) = 9\left(2^{2k-1} + 3^{2k-1}\right) - 5\left(2^{2k-1}\right)\) Where \(\mathrm{f}(k + 1)\) is correct and is clearly a multiple of 5.	A1
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 at the end, at least as given, and all previous marks scored.	A1 cso
	[6]

Alternative (Way 3)

Scheme	Marks
\(\mathrm{f}(n) = 2^{2n-1} + 3^{2n-1}\) is divisible by 5.
\(\mathrm{f}(1) = 2^1 + 3^1 = 5\), Shows that \(\mathrm{f}(1) = 5\).	B1
Assume that for \(n = k\), \(\mathrm{f}(k) = 2^{2k-1} + 3^{2k-1}\) is divisible by 5 for \(k \in \mathbb{Z}^+\).
\(\mathrm{f}(k + 1) + \mathrm{f}(k) = 2^{2(k+1)-1} + 3^{2(k+1)-1} + 2^{2k-1} + 3^{2k-1}\) M1: Attempts \(\mathrm{f}(k + 1) + \mathrm{f}(k)\). A1: Correct expression for \(\mathrm{f}(k + 1)\) (Can be unsimplified)	M1A1
\(= 2^{2k+1} + 3^{2k+1} + 2^{2k-1} + 3^{2k-1}\)
\(= 2^{2k-1+2} + 3^{2k-1+2} + 2^{2k-1} + 3^{2k-1}\)
\(= 4\left(2^{2k-1}\right) + 2^{2k-1} + 9\left(3^{2k-1}\right) + 3^{2k-1}\) Achieves an expression in \(2^{2k-1}\) and \(3^{2k-1}\)	M1
\(= 5\left(2^{2k-1}\right) + 10\left(3^{2k-1}\right)\)
\(= 5\left(2^{2k-1}\right) + 5\left(3^{2k-1}\right) + 5\left(3^{2k-1}\right)\)
\(= 5\mathrm{f}(k) + 5\left(3^{2k-1}\right)\)
\(\therefore \mathrm{f}(k + 1) = 4\mathrm{f}(k) + 5\left(3^{2k-1}\right)\) or \(4\left(2^{2k-1} + 3^{2k-1}\right) + 5\left(3^{2k-1}\right)\) Where \(\mathrm{f}(k + 1)\) is correct and is clearly a multiple of 5.	A1
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 at the end, at least as given, and all previous marks scored.	A1 cso
	[6]

Alternative (Way 4)

Scheme	Marks
\(\mathrm{f}(n) = 2^{2n-1} + 3^{2n-1}\) is divisible by 5.
\(\mathrm{f}(1) = 2^1 + 3^1 = 5\), Shows that \(\mathrm{f}(1) = 5\).	B1
Assume that for \(n = k\), \(\mathrm{f}(k) = 2^{2k-1} + 3^{2k-1}\) is divisible by 5 for \(k \in \mathbb{Z}^+\).
\(\mathrm{f}(k + 1) = \mathrm{f}(k + 1) + \mathrm{f}(k) - \mathrm{f}(k)\)
\(\mathrm{f}(k + 1) = 2^{2(k+1)-1} + 3^{2(k+1)-1} + 2^{2k-1} + 3^{2k-1} - (2^{2k-1} + 3^{2k-1})\) M1: Attempts \(\mathrm{f}(k + 1) + \mathrm{f}(k) - \mathrm{f}(k)\) A1: Correct expression for \(\mathrm{f}(k + 1)\) (Can be unsimplified)	M1A1
\(= 4\left(2^{2k-1}\right) + 9\left(3^{2k-1}\right) + 2^{2k-1} + 3^{2k-1} - \left(2^{2k-1} + 3^{2k-1}\right)\) Achieves an expression in \(2^{2k-1}\) and \(3^{2k-1}\)	M1
\(= 5\left(2^{2k-1}\right) + 10\left(3^{2k-1}\right) - \left(2^{2k-1} + 3^{2k-1}\right)\)
\(= 5\left(\left(2^{2k-1}\right) + 2\left(3^{2k-1}\right)\right) - \left(2^{2k-1} + 3^{2k-1}\right)\)
\(= 5\left(\left(2^{2k-1}\right) + 2\left(3^{2k-1}\right)\right) - \mathrm{f}(k)\) or \(5\left(\left(2^{2k-1}\right) + 2\left(3^{2k-1}\right)\right) - (2^{2k-1} + 3^{2k-1})\) Where \(\mathrm{f}(k + 1)\) is correct and is clearly a multiple of 5.	A1
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 at the end, at least as given, and all previous marks scored.	A1 cso
	[6]