Question
Prove by mathematical induction that \( 5^{2n} – 2^{3n} \) is divisible by 17 for all \( n \in \mathbb{Z}^+ \).
▶️Answer/Explanation
Detail Solution
Step 1: Show that the statement is true for the base case, $n=1$.
$$5^{2(1)}-2^{3(1)}=25-8=17$$, which is divisible by 17.
Step 2: Assume that the statement is true for some integer $k\geq 1$. That is, assume that $5^{2k}-2^{3k}$ is divisible by 17.
Step 3: Show that the statement is true for $n=k+1$. That is, show that $5^{2(k+1)}-2^{3(k+1)}$ is divisible by 17.
Step 4: We can write $5^{2(k+1)}-2^{3(k+1)}$ as $5^{2k+2}-2^{3k+3}=5^2\cdot 5^{2k}-2^3\cdot 2^{3k}=25\cdot 5^{2k}-8\cdot 2^{3k}$.
Step 5: We can rewrite the expression as $25\cdot 5^{2k}-8\cdot 2^{3k}=(17+8)\cdot 5^{2k}-8\cdot 2^{3k}=17\cdot 5^{2k}+8\cdot 5^{2k}-8\cdot 2^{3k}=17\cdot 5^{2k}+8(5^{2k}-2^{3k})$.
Step 6: By the inductive hypothesis, $5^{2k}-2^{3k}$ is divisible by 17. Therefore, $8(5^{2k}-2^{3k})$ is also divisible by 17.
Step 7: Since $17\cdot 5^{2k}$ is clearly divisible by 17, and $8(5^{2k}-2^{3k})$ is divisible by 17, their sum, $17\cdot 5^{2k}+8(5^{2k}-2^{3k})=5^{2(k+1)}-2^{3(k+1)}$, is also divisible by 17.
Step 8: Therefore, by the principle of mathematical induction, $5^{2n}-2^{3n}$ is divisible by 17 for all $n\in Z^{+}$
————Markscheme—————–
Base case: For \( n = 1 \), \( 5^2 – 2^3 = 25 – 8 = 17 \), which is divisible by 17.
Inductive step: Assume \( 5^{2k} – 2^{3k} \) is divisible by 17.
For \( n = k + 1 \):
\( 5^{2(k+1)} – 2^{3(k+1)} = 25 \times 5^{2k} – 8 \times 2^{3k} \)
This can be written as \( 25(5^{2k} – 2^{3k}) + 17 \times 2^{3k} \), which is divisible by 17.
Therefore, by induction, \( 5^{2n} – 2^{3n} \) is divisible by 17 for all \( n \in \mathbb{Z}^+ \).
Question
Consider integers a and b such that a 2 + b2 is exactly divisible by 4. Prove by contradiction that a and b cannot both be odd.
▶️Answer/Explanation
Ans:
Assume that a and b are both odd.
Note: Award M0 for statements such as “let a and b be both odd”.
Note: Subsequent marks after this M1 are independent of this mark and can be awarded.
Then a = 2m + 1 and b = 2n + 1
a2 + b2 ≡ (2m + 1)2 + (2n + 1)2
= 4m2 + 4m + 1 + 4n2 + 4n + 1
= 4 (m2 + m + n2 + n) + 2
(4(m2 + m + n2 + n) is always divisible by 4) but 2 is not divisible by 4. (or equivalent)
⇒a2 + b2 is not divisible by 4, a contradiction. (or equivalent)
hence a and b cannot both be odd.
Note: Award a maximum of M1A0A0(A0)R1R1 for considering identical or two consecutive odd numbers for a and b.
Question
Prove by contradiction that the equation 2x3 + 6x + 1 = 0 has no integer roots.
▶️Answer/Explanation
Ans:
METHOD 1 (rearranging the equation)
assume there exists some α∈ Z such that 2α3 + 6α + 1 = 0
Note: Award M1 for equivalent statements such as ‘assume that α is an integer root of \(2\alpha ^{3} + 6\alpha +1 = 0′.\) Condone the use of x throughout the proof. Award Award M1 for an assumption involving for an assumption involving \(\alpha ^{3} + 3\alpha +\frac{1}{2} = 0.\)
Note: Award M0 for statements such as “let’s consider the equation has integer roots…” ,“let α ∈ Z be a root of 2α3 + 6α + 1 = 0 ….”
Note: Subsequent marks after this M1 are independent of this M1 and can be awarded.
attempts to rearrange their equation into a suitable form
EITHER
Question
Consider integers a and b such that a 2 + b2 is exactly divisible by 4. Prove by contradiction that a and b cannot both be odd.
Answer/Explanation
Ans:
Assume that a and b are both odd.
Note: Award M0 for statements such as “let a and b be both odd”.
Note: Subsequent marks after this M1 are independent of this mark and can be awarded.
Then a = 2m + 1 and b = 2n + 1
a2 + b2 ≡ (2m + 1)2 + (2n + 1)2
= 4m2 + 4m + 1 + 4n2 + 4n + 1
= 4 (m2 + m + n2 + n) + 2
(4(m2 + m + n2 + n) is always divisible by 4) but 2 is not divisible by 4. (or equivalent)
⇒a2 + b2 is not divisible by 4, a contradiction. (or equivalent)
hence a and b cannot both be odd.
Note: Award a maximum of M1A0A0(A0)R1R1 for considering identical or two consecutive odd numbers for a and b.
Question
Use mathematical induction to prove that 5n + 9n+ 2 is divisible by 4, for n ∈ \(\epsilon \mathbb{Z}^{+}\).
▶️Answer/Explanation
Ans
Let f(n) = 5n + 9n + 2 and let Pn be the proposition that f(n) is divisible by 4.
Then f(1) = 16. So P1 is true
Let Pn be true for n = k ie f(k) is divisible by 4
Consider \(f(k+1)=5^{k+1}+9^{k+1}+2=5^k(4+1)+9^k(8+1)+2\)
=\(f(k)+4(5^k+2\chi9^k)\)
Both terms are divisible by 4 so f(k+1) is divisible by 4.
Pk true ⇒ Pk+l true
Since P1 is true, Pn is proved true by mathematical induction for n ∈ \(\mathbb{Z}^+\).