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

Table of contents
- Solution d

Solution

Put

H_{n} = \sum_{k = 0}^{⌊ n /2 ⌋} (k n - k)

; the other summands in the printed sum vanish. The initial values are

H_{0} = 1 = F_{1}

and

H_{1} = 1 = F_{2}

. For

n \geq 2

, Pascal's identity gives

H_{n} = \sum_{k = 0}^{⌊ n /2 ⌋} (k n - 1 - k) + \sum_{k = 1}^{⌊ n /2 ⌋} (k - 1 n - 1 - k) = H_{n - 1} + H_{n - 2} .

For the first sum, when

n

is even its final term is zero; otherwise its range already agrees with

H_{n - 1}

. In the second sum put

j = k - 1

, obtaining

(j n - 2 - j)

for

0 \leq j \leq ⌊(n - 2) /2 ⌋

. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives

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

from the two preceding cases and the Fibonacci recurrence. Hence

k = 0 \sum n (k n - k) = F_{n + 1} (n \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