Problem $2$:

Use the substitution method to show that $T(n)=T(n-1)+n+1$ implies that $T(n)C{n}^2$

as long as $C1$ and $CT(1).$

Problem $3$:

Given the following Python program, prove the loop invariant acc $=\frac{i(i+1)}{2}.$

def litgau$($n$)$:

i $=0$

acc $=0$

while i n:

i $+=1$

acc $+=$ i

return acc

Problem $4$:

Given the following C$-$program, show that the loop invariant $y=2^i-1$ is true. Deduce the

value of $y$ after the function has run.

extern int i;

y$=0$;

for$($i$=0$; in; i$++)\{$

y $+=$ pow$(2,$i$)$;

$\}$