IB DP Maths Topic 10.1 Discrete mathematics-Strong induction. HL Paper 3

Question

The Fibonacci sequence can be described by the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) where \({f_0} = 0,\,{f_1} = 1\).

a.Write down the auxiliary equation and use it to find an expression for \({f_n}\) in terms of \(n\).[7]

b.It is known that \({\alpha ^2} = \alpha  + 1\) where \(\alpha  = \frac{{1 + \sqrt 5 }}{2}\).

For integers \(n\) ≥ 3, use strong induction on the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) to prove that \({f_n} > {\alpha ^{n – 2}}\).[8]

 
▶️Answer/Explanation

Markscheme

attempt to find the auxiliary equation (\({\lambda ^2} – \lambda  – 1 = 0\))     M1

\(\lambda  = \frac{{1 \pm \sqrt 5 }}{2}\)     (A1)

the general solution is \({f_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}\)    (M1)      

imposing initial conditions (substituting \(n\) = 0,1)     M1

A + B = 0 and \(A\left( {\frac{{1 + \sqrt 5 }}{2}} \right) + B\left( {\frac{{1 – \sqrt 5 }}{2}} \right) = 1\)       A1

\(A = \frac{1}{{\sqrt 5 }},\,\,B =  – \frac{1}{{\sqrt 5 }}\)     A1

\({f_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} – \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}\)     A1

Note: Condone use of decimal numbers rather than exact answers.

[7 marks]

a.

let P(\(n\)) be \({f_n} > {\alpha ^{n – 2}}\) for integers \(n\) ≥ 3

consideration of two consecutive values of \(f\)     R1

\({f_3} = 2\) and \({\alpha ^{3 – 2}} = \frac{{1 + \sqrt 5 }}{2}\left( {1.618 \ldots } \right) \Rightarrow {\text{P}}\left( 3 \right)\) is true     A1

\({f_4} = 3\) and \({\alpha ^{4 – 2}} = \frac{{3 + \sqrt 5 }}{2}\left( {2.618 \ldots } \right) \Rightarrow {\text{P}}\left( 4 \right)\) is true    A1

Note: Do not award A marks for values of \(n\) other than \(n\) = 3 and \(n\) = 4.

(for \(k\) ≥ 4), assume that P(\(k\)) and P(\(k\) − 1) are true     M1

required to prove that P(\(k\) + 1) is true

Note: Accept equivalent notation. Needs to start with 2 general consecutive integers and then prove for the next integer. This will affect the powers of the alphas.

\({f_{k + 1}} = {f_k} + {f_{k – 1}}\) (and \({f_k} > {\alpha ^{k – 2}},\,{f_{k – 1}} > {\alpha ^{k – 3}}\))    M1

\({f_{k + 1}} > {\alpha ^{k – 2}} + {\alpha ^{k – 3}} = {\alpha ^{k – 3}}\left( {\alpha  + 1} \right)\)    A1

\( = {\alpha ^{k – 3}}{\alpha ^2} = {\alpha ^{k – 1}} = {\alpha ^{\left( {k + 1} \right) – 2}}\)     A1

as P(3) and P(4) are true, and P(\(k\)) , P(\(k\) − 1) true ⇒ P(\(k\) + 1) true then P(\(k\)) is true for \(k\) ≥ 3 by strong induction      R1

Note: To obtain the final R1, at least five of the previous marks must have been awarded.

[8 marks]

b.

Examiners report

[N/A]

a.

[N/A]

b.

Question

a.The sequence \(\{ {u_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({u_{n + 2}} = 5{u_{n + 1}} – 6{u_n}\) .

Given that \({u_1} = {u_2} = 3\) , obtain an expression for \({u_n}\) in terms of n .[6]

 

b.The sequence \(\{ {v_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({v_{n + 2}} = 4{v_{n + 1}} – 4{v_n}\) .

Given that \({v_1} = 2\) and \({v_2} = 12\) , use the principle of strong mathematical induction to show that \({v_n} = {2^n}(2n – 1)\) .[8]

 
▶️Answer/Explanation

Markscheme

the auxiliary equation is

\({m^2} – 5m + 6 = 0\)     M1

giving \(m = 2,{\text{ 3}}\)     A1

the general solution is

\({u_n} = A \times {2^n} + B \times {3^n}\)     A1

substituting n = 1, 2

\(2A + 3B = 3\)     M1

\(4A + 9B = 3\)     A1

the solution is A = 3, B = –1 giving \({u_n} = 3 \times {2^n} – {3^n}\)     A1

[6 marks]

a.

we first prove that \({v_n} = {2^n}(2n – 1)\) for n = 1, 2     M1

for n = 1, it gives \(2 \times 1 = 2\) which is correct

for n = 2 , it gives \(4 \times 3 = 12\) which is correct     A1

we now assume that the result is true for \(n \leqslant k\)     M1

consider

\({v_{k + 1}} = 4{v_k} – 4{v_{k – 1}}{\text{ }}(k \geqslant 2)\)     M1

\( = {4.2^k}(2k – 1) – {4.2^{k – 1}}(2k – 3)\)     A1

\( = {2^{k + 1}}(4k – 2 – 2k + 3)\)     A1

\( = {2^{k + 1}}\left( {2(k + 1) – 1} \right)\)     A1

this proves that if the result is true for \(n \leqslant k\) then it is true for \(n \leqslant k + 1\)

since we have also proved it true for \(n \leqslant 2\) , the general result is proved by induction     R1

Note: A reasonable attempt has to be made to the induction step for the final R1 to be awarded.

 

[8 marks]

b.

Examiners report

[N/A]

a.

[N/A]

b.
Scroll to Top