Proof by mathematical induction — Question 16

QCAA 2021, Paper 1 · 6 marks

Q16 · 2021 · Technology-freeComplex familiar6 marks

QUESTION 16 (6 marks)

Use mathematical induction to prove that

2^{2n}+3n-1

is divisible by 3 for all

n\in\mathbb Z^+

WORKED SOLUTION

6 marks

ANSWER

The divisibility statement holds for all

n\in\mathbb Z^+

Worked solution

For

n=1

2^2+3-1=6

, divisible by 3. Assume

2^{2k}+3k-1=3m

. For

k+1

2^{2k+2}+3(k+1)-1=4\cdot2^{2k}+3k+2.

Using

2^{2k}=3m-3k+1

, this becomes

12m-9k+6=3(4m-3k+2)

, divisible by 3. Hence the result follows by mathematical induction.

correctly proves the initial statement

[1 mark]

correctly formulates an assumption for

n=k

[1 mark]

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}

[1 mark]

uses previous assumption in the inductive step

[1 mark]

completes proof by determining an expression with a factor of 3 representing the RHS of the inductive step proof

[1 mark]

shows logical organisation, having attempted all steps of the proof, including the use of a suitable conclusion

[1 mark]

One QCAA sample method typeset for web; criterion wording is adapted from the official marking guide.

How many marks did you earn?

Compare your working with the guide above.