The procedure of proof should follow the following format. The answer should lik

Question

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)·(7·2i-1+ (-1)i)

Proof: We prove the statement by induction on i.

Base Case:

We prove that ai= (1/3)·(7·2i-1+ (-1)i) when i=1 and i=2.

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

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

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

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

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

(3)From (1), we know that ak= (1/3)·(7·2k-1+ (-1)k) and ak-1= (1/3)·(7·2k-2+ (-1)k-1).

(4)From (2) and (3), it follows that ak+1= (1/3)·(7·2k-1+ (-1)k) + 2·(1/3)·(7·2k-2+ (-1)k-1)= (1/3)·(7·2k-1+ (-1)k) +(1/3)·(7·2k-1+ 2·(-1)k-1)= (1/3)·(7·2k-1+ (-1)k) +(1/3)·(7·2k-1-2·(-1)k)= (1/3)·(7·2k-1+ 7·2k-1+ (-1)k- 2·(-1)k)= (1/3)·(7·2k- (-1)k) = (1/3)·(7·2k+ (-1)k+1) , which completes the inductive step.

Explanation / Answer

Induction hypothesis: Assume every k-element set has 2k subsets.

Base step: Since the empty set has 1 subset which is itself, and 20 = 1, then a set with 0 elements has 20=1 subsets.

Induction: Now let A = {a1 , a2 , a3 ,..., ak , b}, so that A has (k+1) elements. We partition P(A) into two subcollections where the first contains subsets of A which don’t have b in them and the second contains subsets of A which do have b in them. First Sub-collection will be of form {} ,{a1 }, {a1 , a2 }, {a1 , a2 , ..., ak } ans so on . And on thee other hand seconf sub collection will have elements of these form:  {b}, {a1 , b}, {a1 , a2 , b} ,{a1 , a2 , ..., ak , b}. By induction hypothesis we can claim that first collection will have 2k elements as it is form from set A - {b} and since the size of this set is k which is less than (k+1) we can apply induction hypothesis to claim the number of sub sets to be 2k. Similarly by construction of second subset, it follows that the second collection must have the same number of entries as the first, so it too must have 2k entries.

Since the collection of all subsets of A has been partitioned into these two sub-collections, we can see that A must have 2k + 2k = 2k+1 subsets.(proved)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.