 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/discrete-mathematics-continuous-mathematics-and-probability/2/e/iii/solution

n = 0

, the formula gives

(1 - 1) / 5 = 0 = F_{0}

. At

n = 1

, it gives

(ϕ - ψ) / 5 = 1 = F_{1}

If it holds at

n - 1

and

n

F_{n + 1} = \frac{ϕ ^{n} + ϕ ^{n - 1} - ψ ^{n} - ψ ^{n - 1}}{5} .

The identities

ϕ^{2} = ϕ + 1

and

ψ^{2} = ψ + 1

turn the numerator into

ϕ^{n + 1} - ψ^{n + 1}

. Thus

F_{n} = (ϕ^{n} - ψ^{n}) / 5 for every n \geq 0.

 New to topics? Read the docs here!