 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ia/paper-4/5e/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-29

We prove both identities by mathematical induction. They hold at

n = 1

. Assume they hold at

n

. Using

F_{n - 1} = F_{n + 1} - F_{n}

F_{2 n + 2} = F_{2 n + 1} + F_{2 n} = F_{n}^{2} + F_{n + 1}^{2} + F_{n} (F_{n - 1} + F_{n + 1}) = F_{n + 1} (F_{n} + F_{n + 2}) .

Adding this to

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

and using

F_{n + 2} = F_{n} + F_{n + 1}

gives

F_{2 n + 3} = F_{n + 1}^{2} + F_{n + 2}^{2} .

These are precisely the two assertions with

n

replaced by

n + 1

, completing the induction.

 New to topics? Read the docs here!