 Solution

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

n = 1

. Since

F_{0} = 0

and

F_{1} = 1

, the sum is

- 1 = (- 1)^{1} F_{0} - 1

Suppose the formula holds at

n \geq 1

. Adding the next Fibonacci number with its sign and using the Fibonacci recurrence gives

k = 0 \sum n + 1 (- 1)^{k} F_{k} = (- 1)^{n} F_{n - 1} - 1 + (- 1)^{n + 1} F_{n + 1} = (- 1)^{n + 1} (F_{n + 1} - F_{n - 1}) - 1 = (- 1)^{n + 1} F_{n} - 1.

This is the required successor case. Thus

k = 0 \sum n (- 1)^{k} F_{k} = (- 1)^{n} F_{n - 1} - 1 (n \geq 1) .

 New to topics? Read the docs here!