## Description

ve203 Assignment 8

Q1. Prove that if (an) is a sequence that satisfies a linear homogeneous recurrence

relation of degree 2 whose characteristic polynomial has only one real root α, then there

exists q1, q2 ∈ R such that for all n ∈ N,

an = q1α

n + q2nαn

(4 marks)

Q2. Find an expression for the terms of the sequence (an) that satisfy

an = 2an−1 + an−2 − 2an−3

with a0 = 3, a1 = 6 and a2 = 0.

(2 marks)

Q3. Find an expression for the terms of the sequence (an) that satisfy

an = 5an−1 − 6an−2 + 2n + 2n

2 + n

with a0 = 0, a1 = 4.

(3 marks)

Q4. Find an expression for the terms of the sequence (an) that satisfy

an = 7an−1 − 16an−2 + 12an−3 + n4

n

with a0 = −3, a1 = 2, a2 = 5.

(2 marks)

Q5. For all n ∈ N\{0}, let

an =

Xn

i=1

i

4

By finding a recurrence relation that (an) satisfies and solving that recurrence relation,

find an expression for the terms of the sequence (an).

(2 marks)

Q6. Solve the simultaneous recurrence relations

an = 3an−1 + 2bn−1

bn = an−1 + 2bn−1

with a0 = 1 and b0 = 2.

(3 marks)

Q7. Find an expression for the terms of the sequence (an) that satisfy

an = 2an−1 − 2an−2 + 3n

with a0 = 1, a1 = 2.

(2 marks)

1

Q8. Find a closed formula for the sequences generated by the following generating

functions:

(i) G(x) = x − 1 + 1

1−3x

(ii) G(x) = e

3x

2

− 1

(iii) G(x) = x

1+x+x2

(3 marks)

Q9.

(i) Consider a recurrence relation in the form

f(n)an = g(n)an−1 + h(n)

for n ≥ 1, and with a0 = C. Show that this recurrence relation can be reduced to

a recurrence relation of the form

bn = bn−1 + Q(n)h(n)

where

bn = g(n + 1)Q(n + 1)an and Q(n) = f(1)f(2)· · · f(n − 1)

g(1)g(2)· · · g(n)

(ii) Use (i) to solve the original recurrence relation and obtain

an =

C +

Pn

i=1 Q(i)h(i)

g(n + 1)Q(n + 1)

(iii) Find an expression for the sequence (an) that satisfies

an = (n + 3)an−1 + n with a0 = 1

(6 marks)

2