Processing math: 100%

User interface language: English | Español

Date May 2016 Marks available 6 Reference code 16M.3dm.hl.TZ0.4
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Solve Question number 4 Adapted from N/A

Question

Solve the recurrence relation vn+4vn1+4vn2=0 where v1=0, v2=1.

[6]
a.

Use strong induction to prove that the solution to the recurrence relation un4un1+4un2=0 where u1=0, u2=1 is given by un=2n2(n1).

[8]
b.

Find a simplified expression for un+vn given that,

(i)     n is even.

(ii)     n is odd.

[3]
c.

Markscheme

the auxiliary equation is m2+4m+4=0     M1

m=2    A1

the general solution is

vn=(A+Bn)×(2)n    A1

the boundary conditions give

0= 2(A+B)

1=4(A+2B)    M1

the solution is A=14, B=14     A1A1

so that vn=14(n1)(2)n (or (n1)(2)n2)

[6 marks]

a.

n=1 gives (11)×12=0 which is correct     A1

n=2 gives (21)×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 k     M1

uk+1=4uk4uk1    (M1)

uk+1=4×2k2(k1)4×2k3(k2)    A1

=2k1(2k2k+2) or equivalent     A1

=k2k1    A1

therefore true for nk 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 k1 (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)     un+vn=2n2(n1)+(2)n2(n1)

when n is even un+vn=2n2(n1)+2n2(n1)     M1

=2n1(n1)    A1

(ii)     when n is odd un+vn=0     A1

[3 marks]

c.

Examiners report

This was either done well and completely correct or very little achieved at all (working out v0 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.

Syllabus sections

Topic 10 - Option: Discrete mathematics
Show 214 related questions

View options