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 / b

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

i

Solution

Use mathematical induction. For

n = 1

, the left side is

2^{0} = 1 = 2^{1} - 1

. If the identity holds at

n

, then

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

The base case and induction step establish the geometric series identity

k = 0 \sum n - 1 2^{k} = 2^{n} - 1 (n \geq 1) .

ii

Solution

For the base case

n = 2

,

1 + 1/ 2 > 2

, since multiplying by

2

reduces this to

2 + 1 > 2

. Suppose the claimed inequality holds for some

n \geq 2

. The identity

n + 1 - n = \frac{1}{n + 1 + n} < \frac{1}{n + 1}

then gives

\sum_{k = 1}^{n + 1} \frac{1}{k} > n + \frac{1}{n + 1} > n + 1 .

Thus mathematical induction proves

n < k = 1 \sum n \frac{1}{k} (n \geq 2) .

 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