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.

7. Prove by induction on n: for all integers n 0, for every set S containing exactly n elements, [P(S)2