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.

Proved: https://ideone.com/HRO17U And you didn't specify what $N$ is? — Shahar, Apr 08 '14 at 23:19
Can you clarify what you mean by (a)? If (b) is the proof, what is (a)? — Flowers, Apr 08 '14 at 23:51

score 0 · Answer 1 · answered Apr 08 '14 at 23:57

0

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}$

answered Apr 08 '14 at 23:57

Flowers

1 Answers1