Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 2 / b

Table of contents
- i b
  - Solution i
- ii b
  - Solution ii

i

Solution

The Fibonacci recurrence, with the supplied initial values, is $F_{n + 2} = F_{n + 1} + F_{n}$ for $n \geq 0$ , with

F_{0} = 0, F_{1} = 1

. Two initial values are needed for this second-order linear recurrence relation.

ii

Solution

Use $G_{1} = 0$ and $G_{n + 1} = n G_{n} + n - 1$ for $n \geq 1$ . Indeed,

G_{n + 1} = n! - 1 = n ((n - 1)! - 1) + n - 1 = n G_{n} + n - 1.

The initial value is

0! - 1 = 0

, so the recurrence relation produces the specified factorial sequence.

 Ancestors (11)

 View article source

 Discussion (0)

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