# IB DP Maths Topic 10.11 Recurrence relations. Initial conditions, recursive definition of a sequence. HL Paper 3

## Question

(a)     (i)     Write down the general solution of the recurrence relation $${u_n} + 2{u_{n – 1}} = 0,{\text{ }}n \geqslant 1$$.

(ii)     Find a particular solution of the recurrence relation $${u_n} + 2{u_{n – 1}} = 3n – 2,{\text{ }}n \geqslant 1$$, in the

form $${u_n} = An + B$$, where $$A,{\text{ }}B \in \mathbb{Z}$$.

(iii)     Hence, find the solution to $${u_n} + 2{u_{n – 1}} = 3n – 2,{\text{ }}n \geqslant 1$$ where $${u_1} = 7$$.

(b)     Find the solution of the recurrence relation $${u_n} = 2{u_{n – 1}} – 2{u_{n – 2}},{\text{ }}n \geqslant 2$$, where $${u_0} = 2,{\text{ }}{u_1} = 2$$. Express your solution in the form $${2^{f(n)}}\cos \left( {g(n)\pi } \right)$$, where the functions f and g map $$\mathbb{N}$$ to $$\mathbb{R}$$.

## Markscheme

(a)     (i)     use of auxiliary equation or recognition of a geometric sequence     (M1)

$${u_n} = {( – 2)^n}{u_0}$$ or $$= {\text{A}}{( – 2)^n}$$ or $${u_1}{( – 2)^{n – 1}}$$     A1

(ii)     substitute suggested solution     M1

$$An + B + 2\left( {A(n – 1) + B} \right) = 3n – 2$$     A1

equate coefficients of powers of n and attempt to solve     (M1)

$$A = 1,{\text{ }}B = 0$$     A1

(so particular solution is $${u_n} = n$$)

(iii)     use of general solution = particular solution + homogeneous solution     (M1)

$${u_n} = {\text{C}}{( – 2)^2} + n$$     A1

attempt to find C using $${u_1} = 7$$     M1

$${u_n} = – 3{( – 2)^n} + n$$     A1

[10 marks]

(b)     the auxiliary equation is $${r^2} – 2r + 2 = 0$$     A1

solutions: $${r_1},{\text{ }}{r_2} = 1 \pm {\text{i}}$$     A1

general solution of the recurrence: $${u_n} = {\text{A}}{(1 + {\text{i}})^n} + {\text{B}}{(1 – {\text{i}})^n}$$ or trig form     A1

attempt to impose initial conditions     M1

$$A = B = 1$$ or corresponding constants for trig form     A1

$${u_n} = {2^{\left( {\frac{n}{2} + 1} \right)}} \times \cos \left( {\frac{{n\pi }}{4}} \right)$$     A1A1

[7 marks]

Total [17 marks]

[N/A]

## Question

Andy and Roger are playing tennis with the rule that if one of them wins a game when serving then he carries on serving, and if he loses then the other player takes over the serve.

The probability Andy wins a game when serving is $$\frac{1}{2}$$ and the probability he wins a game when not serving is $$\frac{1}{4}$$. Andy serves in the first game. Let $${u_n}$$ denote the probability that Andy wins the $${n^{{\text{th}}}}$$ game.

State the value of $${u_1}$$.


a.

Show that $${u_n}$$ satisfies the recurrence relation

${u_n} = \frac{1}{4}{u_{n – 1}} + \frac{1}{4}.$


b.

Solve this recurrence relation to find the probability that Andy wins the $${n^{{\text{th}}}}$$ game.


c.

After they have played many games, Pat comes to watch. Use your answer from part (c) to estimate the probability that Andy will win the game they are playing when Pat arrives.


d.

## Markscheme

$$\frac{1}{2}$$     A1

[1 mark]

a.

Andy could win the $${n^{{\text{th}}}}$$ game by winning the $$n – {1^{{\text{th}}}}$$ and then winning the $${n^{{\text{th}}}}$$ game or by losing the $$n – {1^{{\text{th}}}}$$ and then winning the $${n^{{\text{th}}}}$$     (M1)

$${u_n} = \frac{1}{2}{u_{n – 1}} + \frac{1}{4}(1 – {u_{n – 1}})$$     A1A1M1

Note:     Award A1 for each term and M1 for addition of two probabilities.

$${u_n} = \frac{1}{4}{u_{n – 1}} + \frac{1}{4}$$     AG

[4 marks]

b.

general solution is $${u_n} = A{\left( {\frac{1}{4}} \right)^n} + p(n)$$     (M1)

for a particular solution try $$p(n) = b$$     (M1)

$$b = \frac{1}{4}b + \frac{1}{4}$$     (A1)

$$b = \frac{1}{3}$$

hence $${u_n} = A{\left( {\frac{1}{4}} \right)^n} + \frac{1}{3}$$     (A1)

using $${u_1} = \frac{1}{2}$$     M1

$$\frac{1}{2} = A\left( {\frac{1}{4}} \right) + \frac{1}{3} \Rightarrow A = \frac{2}{3}$$

hence $${u_n} = \frac{2}{3}{\left( {\frac{1}{4}} \right)^n} + \frac{1}{3}$$     A1

Note:     Accept other valid methods.

[6 marks]

c.

for large $$n{\text{ }}{u_n} \approx \frac{1}{3}$$     (M1)A1

[2 marks]

Total [13 marks]

d.

## Examiners report

Not all candidates wrote this answer down correctly although it was essentially told you in the question.

a.

Very badly answered. Candidates seemed to think that they were being told this relationship (so used it to find u(2)) rather than attempting to prove it.

b.

This distinguished the better candidates. Some candidates though that they could use the method for homogeneous recurrence relations of second order and hence started solving a quadratic. Only the better candidates saw that it was a combined AP/GP.

c.

The best candidates saw this but most had not done enough earlier to get to do this.

d.

## Question

A recurrence relation is given by $${u_{n + 1}} + 2{u_n} + 1 = 0,{\text{ }}{u_1} = 4$$.

Use the recurrence relation to find $${u_2}$$.


a.

Find an expression for $${u_n}$$ in terms of $$n$$.


b.

A second recurrence relation, where $${v_1} = {u_1}$$ and $${v_2} = {u_2}$$, is given by $${v_{n + 1}} + 2{v_n} + {v_{n – 1}} = 0,{\text{ }}n \ge 2$$.

Find an expression for $${v_n}$$ in terms of $$n$$.


c.

## Markscheme

$${u_2} = – 9$$     A1

[1 mark]

a.

METHOD 1

$${u_{n + 1}} = – 2{u_n} – 1$$

let $${u_n} = a{( – 2)^n} + b$$     M1A1

EITHER

$$a{( – 2)^{n + 1}} + b = – 2\left( {a{{( – 2)}^n} + b} \right) – 1$$     M1

$$a{( – 2)^{n + 1}} + b = a{( – 2)^{n + 1}} – 2b – 1$$

$$3b = – 1$$

$$b = – \frac{1}{3}$$     A1

$${u_1} = 4 \Rightarrow – 2a – \frac{1}{3} = 4$$     (M1)

$$\Rightarrow a = – \frac{{13}}{6}$$     A1

OR

using $${u_1} = 4,{\text{ }}{u_2} = – 9$$

$$4 = – 2a + b,{\text{ }} – 9 = 4a + b$$     M1A1

solving simultaneously     M1

$$\Rightarrow a = – \frac{{13}}{6},{\text{ and }}b = – \frac{1}{3}$$     A1

THEN

so $${u_n} = – \frac{{13}}{6}{( – 2)^n} – \frac{1}{3}$$

METHOD 2

use of the formula $${u_n} = {a^n}{u_0} + b\left( {\frac{{1 – {a^n}}}{{1 – a}}} \right)$$     (M1)

letting $${u_0} = – \frac{5}{2}$$     A1

letting $$a = – 2$$ and $$b = – 1$$     A1

$${u_n} = – \frac{5}{2}{( – 2)^n} – 1\left( {\frac{{1 – {{( – 2)}^n}}}{{1 – – 2}}} \right)$$     M1A1

$$= – \frac{{13}}{6}{( – 2)^n} – \frac{1}{3}$$     A1

[6 marks]

b.

auxiliary equation is $${k^2} + 2k + 1 = 0$$     M1

hence $$k = – 1$$     (A1)

so let $${v_n} = (an + b){( – 1)^n}$$     M1

$$(2a + b){( – 1)^2} = – 9$$ and $$(a + b){( – 1)^1} = 4$$     A1

so $$a = – 5,{\text{ }}b = 1$$     M1A1

$${v_n} = (1 – 5n){( – 1)^n}$$

Note:     Caution necessary to allow FT from (a) to part (c).

[6 marks]

Total [13 marks]

c.

[N/A]

a.

[N/A]

b.

[N/A]

c.

## Question

Solve the recurrence relation $${v_n} + 4{v_{n – 1}} + 4{v_{n – 2}} = 0$$ where $${v_1} = 0,{\text{ }}{v_2} = 1$$.


a.

Use strong induction to prove that the solution to the recurrence relation $${u_n} – 4{u_{n – 1}} + 4{u_{n – 2}} = 0$$ where $${u_1} = 0,{\text{ }}{u_2} = 1$$ is given by $${u_n} = {2^{n – 2}}(n – 1)$$.


b.

Find a simplified expression for $${u_n} + {v_n}$$ given that,

(i)     $$n$$ is even.

(ii)     $$n$$ is odd.


c.

## Markscheme

the auxiliary equation is $${m^2} + 4m + 4 = 0$$     M1

$$m = -2$$    A1

the general solution is

$${v_n} = (A + Bn) \times {( – 2)^n}$$    A1

the boundary conditions give

$$0 = -{\text{ }}2(A + B)$$

$$1 = 4(A + 2B)$$    M1

the solution is $$A = – \frac{1}{4},{\text{ }}B = \frac{1}{4}$$     A1A1

so that $${v_n} = \frac{1}{4}(n – 1){( – 2)^n}{\text{ }}\left( {{\text{or }}(n – 1)( – 2{)^{n – 2}}} \right)$$

[6 marks]

a.

$$n = 1$$ gives $$(1 – 1) \times \frac{1}{2} = 0$$ which is correct     A1

$$n = 2$$ gives $$(2 – 1) \times 1 = 1$$ which is correct     A1

Note:     Must be checked for $$n = 1$$ and 2, other values gain no marks.

assume that the result is true for all positive integers $$\leqslant k$$     M1

$${u_{k + 1}} = 4{u_k} – 4{u_{k – 1}}$$    (M1)

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

$$= {2^{k – 1}}(2k – 2 – k + 2)$$ or equivalent     A1

$$= k{2^{k – 1}}$$    A1

therefore true for $$n \leqslant k \Rightarrow$$ true for $$n = k + 1$$ and since true for $$n = 1$$ and $$n = 2$$, the result is proved by strong induction     R1

Note:     Only award the R1 if at least four of the above marks have been awarded.

Note:     Allow true for $$k$$ and $$k – 1$$ (in 2 places) instead of stronger statement.

Note:     First M1 does not have to be given for further marks to be gained but second (M1) does.

[8 marks]

b.

(i)     $${u_n} + {v_n} = {2^{n – 2}}(n – 1) + {( – 2)^{n – 2}}(n – 1)$$

when $$n$$ is even $${u_n} + {v_n} = {2^{n – 2}}(n – 1) + {2^{n – 2}}(n – 1)$$     M1

$$= {2^{n – 1}}(n – 1)$$    A1

(ii)     when $$n$$ is odd $${u_n} + {v_n} = 0$$     A1

[3 marks]

c.

## Examiners report

This was either done well and completely correct or very little achieved at all (working out $${v_0}$$ for some reason). As expected a few candidates forgot what to do for a repeated root. The varied response to this question was surprising since it is just standard book work.

a.

Strong induction proved to be a very good discriminator. Some candidates knew exactly what to do and did it well, others had no idea. Common mistakes were not checking $$n = 2$$ and 2, trying ordinary induction and worse of all assuming the very thing that they were trying to prove.

b.

Most candidates that had the 2 expressions, knew how to get rid of the minus sign in the 2 cases. Some candidates could not attempt this as they had not completed part (a) although when it was wrong, follow through marks could be obtained.

c.

## Question

Consider the recurrence relation

$${u_n} = 5{u_{n – 1}} – 6{u_{n – 2}},{\text{ }}{u_0} = 0$$ and $${u_1} = 1$$.

Find an expression for $${u_n}$$ in terms of $$n$$.


a.

For every prime number $$p > 3$$, show that $$p|{u_{p – 1}}$$.


b.

## Markscheme

the auxiliary equation is $${\lambda ^2} – 5\lambda + 6 = 0$$     M1

$$\Rightarrow \lambda = 2,{\text{ }}3$$     (A1)

the general solution is $${u_n} = A \times {2^n} + B \times {3^n}$$     A1

imposing initial conditions (substituting $$n = 0,{\text{ }}1$$)     M1

$$A + B = 0$$ and $$2A + 3B = 1$$     A1

the solution is $$A = – 1,{\text{ }}B = 1$$

so that $${u_n} = {3^n} – {2^n}$$     A1

[6 marks]

a.

$${u_{p – 1}} = {3^{p – 1}} – {2^{p – 1}}$$

$$p > 3$$, therefore 3 or 2 are not divisible by $$p$$     R1

hence by FLT, $${3^{p – 1}} \equiv 1 \equiv {2^{p – 1}}(\bmod p)$$ for $$p > 3$$     M1A1

$${u_{p – 1}} \equiv 0(\bmod p)$$     A1

$$p|{u_{p – 1}}$$ for every prime number $$p > 3$$     AG

[4 marks]

b.

[N/A]

a.

[N/A]

b.

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


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


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 .


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


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.