The procedure of proof should follow the following format. The answer should like that.

Example

Consider the sequence a1, a2, a3,... given by a1= 2, a2= 5, and ai= ai-1+ 2ai-2for all i3.

Prove that, for all i1:ai= (1/3)(72^i-1+ (-1)ⁱ)

Proof: We prove the statement by induction on i.

Base Case:

We prove that ai= (1/3)(72^i-1+ (-1)ⁱ) when i=1 and i=2.

When i=1: we are given that a1= 2,and we see that (1/3)(72^i-1+ (-1)ⁱ) = (1/3)(7-1) = 2, as required.

When i=2: we are given that a2= 5,and we see that (1/3)(72^i-1+ (-1)ⁱ) = (1/3)(72+1) = (1/3)15 = 5, as require

Inductive step: We prove that, for all k2,if aj= (1/3)(72^j-1+ (-1)^j) for all j{1,...,k},then ak+1= (1/3)(72^k+ (-1)^k+1).

(1)Let k be an arbitrary positive integer such that k2.Assume thataj= (1/3)(72^j-1+ (-1)^j) for all j{1,...,k}.

(2)Since k2, we know that k+13, so the given recursive formula states that a_k+1= a_k+ 2a_k-1.

(3)From (1), we know that a_k= (1/3)(72^k-1+ (-1)^k) and a_k-1= (1/3)(72^k-2+ (-1)^k-1).

(4)From (2) and (3), it follows that a_k+1= (1/3)(72^k-1+ (-1)^k) + 2(1/3)(72^k-2+ (-1)^k-1)= (1/3)(72^k-1+ (-1)^k) +(1/3)(72^k-1+ 2(-1)^k-1)= (1/3)(72^k-1+ (-1)^k) +(1/3)(72^k-1-2(-1)^k)= (1/3)(72^k-1+ 72^k-1+ (-1)^k- 2(-1)^k)= (1/3)(72^k- (-1)^k) = (1/3)(72^k+ (-1)^k+1) , which completes the inductive step.

8. (a) Prove the following statement by induction on n: for all n 1, if n + l onore iterns are placed in at tnost n boxes, then at least one of the boxes must contain at least two items. (b) Suppose that eight hockey teams are entered in a round-robin tournament, which means that each team plays every other team exactly once. Assume that no ties are allowed (e.g., al ties will go to a penalty shootout). Prove that if no team loses all of its games, then at least two teams wil finish the tournament with the same number of wins Hinl: use the facl proven in part (a))