Homework 6, due on Wednesday, May 20 by 11:59pm PST

• Chapter 11 (11.2, 11.4, 11.6)
• Chapter 12 (12.2, 12.5)
• Problems III on p. 182-187 (14[You may use the fact that any positive integer can be written as a product of an odd integer and a power of 2.], 19)
• For any nonnegative integer \(n\), show that \(\displaystyle\sum_{i=0}^n\binom{n}{i}2^i=3^n\).
• For any positive integer \(n\), prove that \(\displaystyle\sum_{\substack{i=0\\i \text{ is even}}}^n\binom{n}{i}=\sum_{\substack{i=0\\i \text{ is odd}}}^n\binom{n}{i}\). Hint for one way of proving this: If \(X\) is set of cardinality \(n\), find a bijection between the set of elements of \(\mathcal{P}(X)\) of even cardinality and the set of elements of \(\mathcal{P}(X)\) of odd cardinality.