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$$.

Write down the auxiliary equation and use it to find an expression for $${f_n}$$ in terms of $$n$$.

[7]
a.

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]
b.

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.

[N/A]

a.

[N/A]

b.

Question

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]
a.

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]
b.

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.

[N/A]

a.

[N/A]

b.