Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 2 / c

Table of contents
- Solution c

Solution

The initial values of the two sequences agree:

c_{0} = d_{0} = 1

and

c_{1} = - 1 + c_{0} = 0 = d_{1}

. For

n \geq 2

, use the first-order recurrence relation at

n

and

n - 1

:

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

Therefore

c_{n}

satisfies exactly the same derangement recurrence as

d_{n}

. By strong induction, equality of the preceding two terms implies equality of the next term. Consequently

c_{n} = d_{n} for every n \geq 0.

The first-order recurrence relation therefore also counts derangements.

 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