MTP 621
Homework 5

Due April 22:

skim chapters 15, 17, and 19, and vote on which of these topics to cover on April 29.

The real homework, assigned 16 Apr, due 29 Apr, to be done individually

Many of these problems can be "auto-graded": you can use the "Submit" program to try them out, not sending the report to me, and if everything works fine, you can then "Submit" them to me too. So you should get a 100% score on all of these problems. If you have a used copy of the software, "Submit" may not work, in which case you can just e-mail me, attaching the files that you would have submitted; you don't get the same instant feedback, so be sure you're confident of your answers before sending them to me.

For the induction proofs, you'll need to write down the answers in English and give/mail them to me. These induction proofs are to be written informally, but you may (if you wish) use Fitch bars to keep track of the beginnings, assumptions, and ends of subproofs.

• Do but don't turn in all of the "You Try It" exercises in chapter 13
• 13.2 through 13.6 (auto-graded)
• 13.11 through 13.15 (auto-graded)
• 13.17 and 13.18 (auto-graded)
• 13.23 through 13.27 (auto-graded)
• 13.28, 13.30, 13.31 (auto-graded; I don't like 13.29 because it's invalid in the empty world)
• 16.1, 16.4, 16.6, 16.16, 16.17, 16.18 (on paper or e-mail)

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

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

• 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.