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

Table of contents
- i c
  - Solution i
- ii c
  - Solution ii

i

Solution

Use mathematical induction, starting at

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) .

ii

Solution

Fix

n \geq 1

and use mathematical induction on

m

with two initial cases, as appropriate for the second-order Fibonacci recurrence. At

m = 0

, the right side is

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

. At

m = 1

, it is

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

.

If the identity holds at

m

and

m + 1

, then

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

Hence the induction establishes

F_{n + m} = F_{n - 1} F_{m} + F_{n} F_{m + 1} (n \geq 1, m \geq 0) .

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version