0 = 0 {

reflexivity of equality }

Induction Step:

arithmetic and reflexivity of equality }

(b) Basis:

) = |0 2 (0+1) 2

one-point rule to simplify the summation, arithmetic }

0 = 0 = {

arithmetic and reflexivity of equality }

Induction Step:

l ^ k ^ n : k 3 ) + (n+l) 3 = |(n+l) 2 (n+2) 2 ( Z k : l ^ k ^ n : k 3 ) = |n 2 (n+l) 2 . |n 2 (n+l) 2 + (n+1) 3 = |(n+l) 2 (n+2) 2 arithmetic and reflexivity of equality }

(c) Basis:

x-l one-point rule to simplify the summation,

arithmetic }

x * i, arithmetic and reflexivity of equality } true . Induction Step:

,n+l _

:xk) =

x-l -1 x-l arithmetic and reflexivity of equality }

true (d) Basis:

arithmetic }

true Induction Step: l + (n+l)xx transitivity of ^ (heading towards using the induction hypothesis, we introduce the middle term

nxx) ) }

nxx) ^ 1 + (n+l)xx assume that (l+x) n ^ 1 + nxx . x > - 1, so 1 +x > 0. Multiplication by a positive

number is monotonic. That is, nxx) ^ l + (n+l)xx { { true . (e) Basis: : -r i- \ - -^kx(k+l)/ 0+1 empty-range rule to simplify the summation, arithmetic on the right side } true . Induction Step: kx(k+l) range splitting }

1 + x + nxx + nxx ^ 1 + x + nxx nxx2 ^ 0. Addition is monotonic. }

* ! 1 '

, , ,. \ /

-. .

kx(k+l)/ n n+1 n+1 (n+l)x(n+2) n+2 { arithmetic and reflexMty of equality }

(f) Basis: empty-range rule to simplify the summation, arithmetic }

0 = 0 {

reflexivity of equality }

312 Induction Step: 'zfcil^fc { range splitting }

.

n+2 2n {

n+l _ n+3 ~~ 2 n+1 ~~ 2 n+1 arithmetic and reflexivity of equality }

Solution 12.13. Basis: the basis is the case n = 1. This is because there are individual definitions of F.O and F.I. We have F.(l + l ) x F . ( l - l ) - (F.I) 2

definition } arithmetic } arithmetic }

{ -1

Induction Step: care must be taken in the induction step when expanding the definition of F. Assuming that n ^ 1, the definitions of F. (n+2) and F.(n+l) are given by the rule F.(k+2) = F.(fc+l) + F.fe, for all k, k ^ 0. (This is not the case for the definition of F.n.) { { arithmetic } definition: F.(k+2) = F.(k+l) + F.k applied to the cases k = n and k = n-1. } (F. (n+l) + F.n) x F.n - (F.n + F.(n-l)) xF.(n+l) { arithmetic }

F.(n+2)xF.n - (F.(n+l)) 2

(F.n)2 - F.(n-l)x { -(-l) n { (-l)

The proof uses simple induction only. Solution 12.14. The first step is invalid in the case that n = 0.

This is true by virtue of the empty-range rule (since N < i < N is false) and simple properties of arithmetic. The termination condition is valid if ( K f c ^ N A sxXk = (I.i:k^i<N:a[i]xXi) => 5 = ( E i : Q ^ i < N : a [ i ] x X i } . D A -.(fe>0)

This is clearly true as 0 < k < N A ->(fe > 0) reduces to 0 = k < N, Solution 13.15. The invariant is established by the assignment

independently of the value of z. As the reader will have seen in solving Exercise 10.21, we also have { 0 < k = K A yxzk = XM }