Strong Principle of Mathematical Induction

• Read carefully pages 161 through 164 (section 6.4)
• Some key questions to answer:
  1. What does the strong principle of mathematical induction state? How is it different from the other principles of mathematical induction?
  2. What does the more general version of the strong principle of mathematical induction say?
  3. What are recursively defined sequences? How is the strong principle of mathematical induction related to them?
  4. If a sequence is defined recursively by \(a_1 = 1\), \(a_2=4\), \(a_n = 2a_{n-1} - a_{n-2} + 2\) for all \(n\geq 3\), then show that in fact \(a_n = n^2\) for all \(n\).
  5. Show that for each integer \(n\geq 8\) there are nonnegative integers \(a,b\) such that \(n = 3a + 5b\).
  6. The Fibonacci numbers are defined via the recursive relation \(F_1 = 1\), \(F_2 = 1\), then for each \(n\geq 2\), \(F_{n} = F_{n-1} + F_{n-2}\).
     • Define the number \(\varphi = \frac{1+\sqrt{5}}{2}\), and also denote \(\bar\varphi = \frac{1-\sqrt{5}}{2}\). Show that both \(\varphi\) and \(\bar\varphi\) satisfy the equation \(x^2 = x + 1\). (this is technically not directly related to the Fibonacci numbers). \(\varphi\) is known as the golden ratio and has many interesting properties.
     • Show more generally that for every \(n\geq 2\) both \(\varphi\) and \(\bar\varphi\) satisfy the equation \(x^n = x^{n-1} + x^{n-2}\).
     • Show by the principle of strong induction that for every \(n\geq 1\) we have \(F_n = \frac{1}{\varphi - \bar\varphi}\left(\varphi^n - \bar\varphi^n\right)\). If you think about it for a minute, it’s remarkable that this formula even produces integers.
• Practice problems from section 6.4 (page 167): 6.41, 6.43, 6.44, 6.45
• Challenge: 6.46, 6.47