Tutorial

Exercise 1

$$\frac{\frac{\frac{}{10{\Downarrow }_{P}10}(n)\frac{\frac{}{3{\Downarrow }_{P}3}(n)\frac{\frac{}{3{\Downarrow }_{P}3}(n)\frac{}{3{\Downarrow }_{P}3}(n)}{x\ast x\{x\to 3\}\Downarrow 9}\frac{\frac{\frac{}{10{\Downarrow }_{P}10}(n)\frac{}{9{\Downarrow }_{P}9}(n)}{10\ge 9\Downarrow \text{true}}(bop)\frac{}{10{\Downarrow }_{P}10}(n)}{\text{if }x\ge y\text{ then }x\text{ else }y\{x\to 10,y\to 9\}{\Downarrow }_{P}10}(if)}{\text{sqr}(3){\Downarrow }_{P}9}}{\text{max}(10,\text{sqr}(3)){\Downarrow }_{P}10}(f{n}_{\text{val}})\frac{[..]}{[..]}}{\text{sqr}(\text{max}(10,\text{sqr}(3))){\Downarrow }_{P}100}(f{n}_{\text{val}})$$

Exercise 2

Prove ${\sum }_{i=1}^n(2i-1)=n^2$.

1. Base Case: $LHS=(2(1)-1)=1$ $RHS=n^2=(1{)}^2=1$
2. Induction Hypothesis: Assume ${\sum }_{i=1}^n(2i-1)=n^2$
3. Induction Step: $$\begin{array}{rl}LHS& =\sum _{i=1}^{n+1}(2i-1)\\ & =\sum _{i=1}^n(2i-1)+(2(n+1)-1)\\ & =n^2+2n+1\\ & =(n+1{)}^2\text{ as required}\end{array}$$