General Principle of Mathematical Induction

• Read carefully pages 151 through 158 (section 6.2)
• Some key questions to answer:
  1. The first extension to the principle of mathematical induction concerns the start point of the induction (some other (possibly negative) fixed integer \(m\) rather than \(1\)). What does the theorem say precisely, and how is it proven?
  2. Explain why we needed this new more general principle of mathematical induction to prove result 6.9. How could we have proved it if all we could use was the originla principle?
  3. Prove that for every natural number \(n\geq 5\) we have \(2^n > n^2\).
  4. Prove that for every non-negative integer \(n\) we have \(3|(2^{2n} - 1)\).
  5. Prove that for every non-negative integer \(n\) we have \(9|(4^{3n} - 1)\).
  6. Prove that for every positive integer \(n\) we have that the product of all odd integers up to \(2n-1\) equals \(\frac{(2n)!}{2^n n}\).
  7. Prove that for every \(n\geq 2\) we have that for every sets \(A_1,\ldots, A_n\) we have \(\overline{A_1\cup A_2\cup\cdots\cup A_n} = \overline{A_1}\cap\overline{A_2}\cap\cdots\cap \overline{A_n}\).
  8. Prove that for every \(n\), if \(A\) is a set with \(n\) elements then the powerset \(P(A)\) has \(2^n\) elements.
• Practice problems from section 6.2 (page 166): 6.17, 6.18, 6.19, 6.21, 6.23, 6.29
• Challenge problems (optional): 6.31, 6.32