 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/discrete-mathematics-continuous-mathematics-and-probability/2/c/ii/solution

Let

ϕ = (1 + 5) /2

, the golden ratio. Since

ϕ^{2} = ϕ + 1

ϕ^{n}

gives

ϕ^{n + 2} = ϕ^{n + 1} + ϕ^{n}

. Adding this recurrence relation to the one for

A_{n}

yields

B_{n + 2} = B_{n + 1} + B_{n}, B_{0} = 3, B_{1} = 2 + ϕ .

Thus the extra exponential term changes the initial values, but not the linear recurrence relation.

 New to topics? Read the docs here!