Math 355
Homework 7

Assigned Dec. 8, due Dec. 15, to be done individually

Note: The syllabus said that anything turned in after the last day of class (Dec. 12) would get a zero. I am hereby changing that rule, so you have a reasonable amount of time to do this assignment. Don't bother turning in homeworks 1-6 after Dec. 12, but homework 7 can be turned in as late as midnight, Dec. 15.

Note: These proofs should be done informally, but feel free to use Fitch bars to keep track of the beginnings, assumptions, and ends of subproofs if you wish.

1. Problem 16.1 (on paper)
2. Problem 16.16 (on paper)

3. Prove by mathematical induction that, for all numbers r ≠ 1, for all natural numbers n,

   1 + r + r² + r³ + ... + rⁿ = (rⁿ⁺¹-1)/(r-1)

4. The Fibonacci numbers are defined as follows:

   • F₀ = 0
   • F₁ = 1
   • F_n = F_n-1 + F_n-2 for n ≥ 2
   Prove that for all natural numbers n,

   F_n < 2ⁿ.

   Hint: Since Fibonacci numbers depend on not only the previous one but the previous two, you'll probably find the Least Number Principle more useful than ordinary natural-number induction.

5. Prove, similarly, that for all natural numbers n ≥ 3,

   F_n > 1.5ⁿ/2 .