Induction Proof of Loop Invariance Given the Invariance

67 Views Asked by At

Consider the following program segment

i=1
total = 1

while i<n
  i = i + 1
  total = total + i

Let p be the proposition "total = $\frac{{i}{(i+1)}}{2}$ " and $ i ≤ n $ Use mathematical induction to prove the that p is a loop invariant.

Having issues simplifying and solving the problem.

  1. I claim that the loop invariant is $t=\frac{{i}{(i+1)}}{2}$

  2. I start off with the Base Case of i=1 and t=1 which proves to be true $$1 = \frac{{1}{(1+1)}}{2}$$

  3. Now I let tB and iB be the values at the end of the xth iteration of the loop and tA and iA be the vales after (x+1)th iteration of the loop

  4. So my Induction Hypothesis is that my loop invariant holds at the end of the xth iteration

$$IH: t_b = \frac{{i_b}{(i_b+1)}}{2}$$

Whereas

tA = tB + iB

iA = iB + 1

And my guard condition is ib ≤ n

So then we would have

$$ t_a = t_b+i_a $$ $$ = \frac {{i_b}{(i_b+1)}}{2} + ia $$ $$ = \frac {{i_b}{(i_a)}}{2} + \frac{2i_a}{2}$$ $$ = \frac {{i_b}{(i_a)}+{2i_a}}{2}$$ $$ = \frac {{i_a}{(i_b}{}+{i_a)}}{2}$$

And now I'm stuck. I'm having trouble understanding where to use the updated variables in the Induction proofs as one of the variables relies on its previous iteration. Thank you for your time everyone.

Update I've figured out subscripts