 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/2/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

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.

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

 New to topics? Read the docs here!