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.
Prove by mathematical induction that, for all numbers r ≠ 1, for all natural numbers n,
1 + r + r^{2} + r^{3} + ... + r^{n} = (r^{n+1}-1)/(r-1)
The Fibonacci numbers are defined as follows:
F_{n} < 2^{n}.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.
Prove, similarly, that for all natural numbers n ≥ 3,
F_{n} > 1.5^{n}/2 .