Show that this summation is an invariant of the loop in algorithm

Question

I'm having trouble with induction with this specific problem.

a) Show that $\sum_{i=0}^k 2^i = 2^{k+1} - 1$ is an invariant of the loop in algorithm

begin
 k := 0
 while 0 ≤ k do
   k := k + 1
 end

b) Can you use (a) to prove that summation for every $k$ in $\mathbb{N}$? Explain.

I am unsure where to start. I could do specific examples such as when $k = 1$ and such. But how do I show the invariant. Thank you.

Answer 1

Assume it is true for numbers between $1$ and $k$, then check for $k+1$.

$$\sum_{i=0}^{k+1} 2^i = \left(\sum_{i=0}^{k} 2^i\right) + 2^{k+1} = (2^{k+1} - 1) + 2^{k+1} = 2^{k+2} - 1$$

Since it is true for $k=1$, it is true for all $k\in\mathbb{N}$