 Solution

ID: 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/i/solution

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

 New to topics? Read the docs here!