This problem is 42 in section 9.7 of Discrete Math With applications by susan ep

Question

This problem is 42 in section 9.7 of Discrete Math With applications by susan epp 4th edition. The problem is:

Use mathematical induction to prove that for all integers

n ? 1, if S is a set with n elements, then S has the same

number of subsets with an even number of elements as with

an odd number of elements. Use this fact to give a combinatorial

argument to justify the identity of exercise 36.

where 36 is the picture attached.

Explanation / Answer

base case: n=1. This is true for n=1.since for a set with only one element say x contain two subsets one with 0 elements (empty set ) and other with the set containing x with one element . Hence even sets =oddsets = 1 for n=1. so this is true for base case Induction case: let us assume this statement is true for all kevensets in S= evensetsin Q + Oddsets in Q (since adding x to oddset in Q results in a evensets in S and all evensets of Q without x are evensets in S) and also oddsets in S= evensetsin Q + Oddsets in Q(similar reason as above) Hence evensets in S= oddsets in S So by induction the given statement is true. 36.) here (n 0) respresents the number of subsets with 0 elements of set containing n elements similarly (n k) respresents the number of subsets with k elements of set containing n elements From the above statement which was proved by induction No of sets containing even number of elements are equal to number of sets containing odd number of elements => (n 0)+(n 2) + (n 4) + ..... =(n 1)+(n 3) + (n 5) + ..... => (n 0) - (n 1) + (n 2) +.....+(-1)^n (n n) =0 Hence proved

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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