May 2023 Paper 2 Q12
12. Prove by induction that, for all positive integers \(n\), \(\displaystyle\sum_{r=1}^{n}2^{r-1}r=2^n(n-1)+1\). [5]
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •1 | show true for \(n=1\) 1 | \((\text{LHS}=)\,2^{1-1}\times1=1\) \((\text{RHS}=)\,2^1(1-1)+1=1\) so result is true when \(n=1\) |
| •2 | assume statement true for \(n=k\) AND consider whether statement true for \(n=k+1\) 2,5 | suitable statement AND \(\displaystyle\sum_{r=1}^{k}2^{r-1}r=2^k(k-1)+1\) AND \(\displaystyle\sum_{r=1}^{k+1}2^{r-1}r=\cdots\) |
| •3 | state sum to \(k+1\) terms using inductive hypothesis 3 | \(2^k(k-1)+1+(k+1)2^{k+1-1}\) or \(2^k(k-1)+1+(k+1)2^k\) |
| •4 | take out common factor of \(2^k\) and simplify 4 | \(2^k\cdot2k+1\) |
| •5 | express sum explicitly in terms of \((k+1)\) or achieve stated aim/goal AND communicate 5,6,7 | \(2^{(k+1)}\left(k+1-1\right)+1\) AND If true for \(n=k\) then true for \(n=k+1\). Also true for \(n=1\) therefore, by induction, true for all positive integers \(n\) |
| (5) |
Notes:
- “RHS = 1, LHS = 1” and/or “True for \(n=1\)” are insufficient for the award of •1. Where a candidate does not independently evaluate LHS and RHS, •1 may still be awarded.
- For •2, sufficient phrases for \(n=k\) contain:
- ‘If true for...’; ‘Suppose true for…’; ‘Assume true for…’.
For •2 insufficient phrases for \(n=k\) contain:
- ‘Consider \(n=k\)’, ‘assume \(n=k\)’, ‘assume \(n=k\) is true’ and ‘True for \(n=k\)’.
A sufficient phrase for the award of •2 may appear at •5.
For •2, accept:
assume true for \(n=k\) AND \(\displaystyle\sum_{r=1}^{k}2^{r-1}r=2^k\left(k-1\right)+1\) AND “Aim/goal: \(\displaystyle\sum_{r=1}^{k+1}2^{r-1}r=2^{k+1}\left(k+1-1\right)+1\)”
For •2 unacceptable phrases for \(n=k+1\) contain:
- “Consider true for \(n=k+1\)”, “true for \(n=k+1\)”,
- “\(\displaystyle\sum_{r=1}^{k+1}2^{r-1}r=2^{k+1}\left(k+1-1\right)+1\)” (with no reference to aim/goal and no further processing).
- Since •3 may be awarded directly after •2, exercise leniency in relation to intermediate notation where this has been provided, eg the handling of sigma notation.
- •4 is unavailable to candidates who arrive at \(2^k\cdot2k+1\) without algebraic justification.
- •5 is unavailable to candidates who have not been awarded •4.
- Full marks are available to candidates who state an aim/goal earlier in the proof and who subsequently achieve the stated aim/goal, provided \(2^{k+1}\left(k+1-1\right)+1\) appears at some point.
- Following the required algebra and statement of the inductive hypothesis, the minimal acceptable response for •5 is: “Then true for \(n=k+1\), but since true for \(n=1\), then true for all \(n\)” or equivalent.