Question 16
Use mathematical induction to prove that $2^{2n}+3n-1$ is divisible by $3\ \forall n\in Z^+$.
[6 marks]The next case holds the last one plus a multiple of 3
Each square is one unit. Watch the case $n=2$ split into groups of three, then watch the case $n=3$ rearrange so the case $n=2$ appears inside it.
The same thing happens at every step. Since $2^{2(k+1)}=4\times2^{2k}$, one copy of $2^{2k}$ goes back into the previous case and the other three copies, plus 3, are a multiple of 3.
Build the case after the assumption, one move at a time
Pick a value of $k$. First choose the correct way to rewrite the power, then choose how to bring in the assumption. The bars show the case $n=k+1$ split into the case $n=k$ and the new part.
The bars are to scale, except the grey piece for the extra 3, which is drawn wider so you can see it.
Which expression equals $2^{2(k+1)}$? Pick one and the numbers will check it.
That adds 2 to the value of the power, but the 2 belongs in the index. With these numbers,
That adds only 1 to the index. The index is $2n$, so it goes up by 2 when $n$ goes up by 1. With these numbers,
Yes. The index law gives $2^{2k+2}=2^2\times2^{2k}$. With these numbers,
Three of the four copies of $2^{2k}$ go into the new part. The fourth copy joins $3k-1$ to make the assumption, which you replace with $3m$.
Rearrange the assumption to make $2^{2k}$ the subject, then substitute. The terms in $k$ collect into a multiple of 3 as well.
Both routes end with 3 times the same positive integer:
Work through the solution one mark at a time
Try each step yourself before you reveal it. This follows the QCAA’s sample response, which splits the assumption off the expression for $n=k+1$.
Start by writing what you are proving as an equation. Divisible by 3 means equal to 3 times a positive integer.
$$\begin{aligned}&2^{2n}+3n-1=3m,\\&\text{for some }m\in Z^+\end{aligned}$$
The positive integers start at 1, so let $n=1$.
$$\begin{aligned}2^2+3-1&=6\\&=3\times2\end{aligned}$$
So the proposition is true for $n=1$. An equivalent setting out of the proof of the initial statement is accepted.
Marker: correctly proves the initial statement
Assume the proposition is true for $n=k$, where $k$ is a positive integer. Write it with $k$ in place of $n$ and name the multiple.
$$\begin{aligned}&2^{2k}+3k-1=3m,\\&\text{for some }m\in Z^+\end{aligned}$$
An equivalent assumption is accepted, such as $2^{2k}+3k-1=3q$ or the rearranged form $2^{2k}=3m-3k+1$.
Marker: correctly formulates an assumption for $n=k$
Let $n=k+1$. Substitute it into the left-hand side, expand the index, then use the index law $a^{x+y}=a^x\times a^y$ to pull out a factor of $2^{2k}$.
$$\begin{aligned}&2^{2(k+1)}+3(k+1)-1\\&=2^{2k+2}+3k+3-1\\&=2^2\times2^{2k}+3k-1+3\end{aligned}$$
Keeping $3k-1$ together is deliberate, because it is part of the assumption. An equivalent expression such as $4\times2^{2k}+3k+2$ is also accepted. This mark can be implied by your later working.
Marker: correctly establishes an expression representing the LHS of the inductive step proof and uses an index law to establish a term with a factor of $2^{2k}$
Write $2^2\times2^{2k}$ as one copy of $2^{2k}$ plus three copies. The one copy completes the assumption, so replace that group with $3m$.
$$\begin{aligned}&=\underbrace{2^{2k}+3k-1}_{=\,3m}+3\times2^{2k}\\&\qquad+3\\&=3m+3\times2^{2k}+3\end{aligned}$$
Say in your working that this line uses the assumption. Another use of the assumption is accepted too. Substituting $2^{2k}=3m-3k+1$ gives $4(3m-3k+1)+3k+2$, which simplifies to $4(3m)-9k+6$. This mark can be implied by your later working, and follow-through marks are allowed for errors in earlier working.
Marker: uses previous assumption in the inductive step
Every term now has a factor of 3. Take it out and name what is left as a positive integer.
$$\begin{aligned}&=3\left(m+2^{2k}+1\right)\\&=3p,\ \text{for some }p\in Z^+\end{aligned}$$
Here $p=m+2^{2k}+1$ is a positive integer because $m$ and $2^{2k}$ are. Equivalent expressions such as $3(4m-3k+2)$ or $3(4m+2)-3(3k)$ are accepted.
Marker: completes proof by determining an expression with a factor of 3 representing the RHS of the inductive step proof
Finish in words. Mention the case $n=k+1$ and the initial statement.
This mark is for the whole proof. The marker looks for statements such as “$n=1$”, “$n=k+1$” and “assume $n=k$ is true”, for the requirement that the parameter is a positive integer (such as $m\in Z^+$), and for equals signs that only join things that are actually equal.
Marker: shows logical organisation, having attempted all steps of the proof, including the use of a suitable conclusion
Each phrase of the question gave you something
The question is one line long and worth 6 marks, with no parts to guide you. You have to see for yourself that $2^{2(k+1)}$ becomes $4\times2^{2k}$ and then decide how to break that 4 up so the assumption appears inside the expression. The index of $2n$ makes the index law step less automatic than in a proof with $3^n$. It is still familiar, because “use mathematical induction to prove … is divisible by” names a proof you have practised, and the four parts are the same every time.
The subject report for this year lists “mathematical induction for proving divisibility results in familiar situations” among the things students responded well to. If I had to guess where you might lose marks, it would be the index law in step 3. Writing $2^{2(k+1)}$ as $2\times2^{2k}$ or as $2^{2k}+2$ breaks every line after it. The last mark is the other one to watch. The marking guide asks for “$n=1$”, “$n=k+1$” and “assume $n=k$ is true” statements, for a positive integer parameter such as $m\in Z^+$ and for a suitable conclusion, so a proof that stops at $3p$ gives that mark away.
Only mark this done when you could do it without help. Reading the solution does not count.
Question wording and marking-guide steps are from the 2021 QCAA Specialist Mathematics external assessment, © State of Queensland (QCAA) 2021, licensed under CC BY 4.0, and have been adapted. Tangent Tuition is not affiliated with the QCAA.
Spot a mistake on this page? Report it