Homework 7: Induction (Mathematical, Strong, and Structural)

Due 05.Mar.22 (Tue)

Before you tackle the homework, remind yourself of our general hw policies (now includes proof-by-induction tips ). In particular, you don't need to show your work when only a short answer is required (though doing so might garner more partial credit if the answer is wrong).

Reading: Rosen 3.3-3.5.

1. (6pts) Section 3.2, #32 (p.237): Specific sets countable? (Delayed from hw06.)
   Write your function in standard mathematical notation, not English. (Hint: Standard notation includes floor and ceiling, as well as a case statement (big-curly-left-bracket).)
   Be sure to convince yourself that the correspondence you give really is both one-to-one and onto!
2. (4pts) Section 3.3, # 8 (p.253): ∑i³.
3. (4pts) Section 3.3, #18 (p.253): ∑k^-2 < 2-1/n.
4. (1pt ) Section 3.3, #50 (p.255): False proof: ∑ i = (n+0.5)²/2.
5. (2pts) Section 3.3, #52 (p.255): False proof: (max(x,y)=n) ⇒ (x=y).
6. (4pts) Section 3.4, #18 (p.271): powers of [1 1 \ 1 0].
   See labbies or TAs, or read Rosen, for matrix multiplication (p.198) and the Fibonacci numbers f_i (p.259).
7. (4pts) Chpt 3 Supplementary exercise (p.294), #44; counting jigsaw moves.
   Note: strong induction really is relevant here; if you didn't use it, think about some jigsaw-solving moves that don't actually correspond to your non-strong apporach.
8. (5pts) section 3.4, #35 plus #36 (p.272): string reversal.
   Hint: only induct on one of the two strings. Thus you'll have a statement ``∀ w₁ ∈ {0,1}^*, …''. Whether this statement is inside or outside of your parameterized induction statement P() is up to you, but make your choice clear.
9. (2pts) section 3.4, #38 (p.272): def'n of palindromes.
10. (4pts) section 3.4, #44 (p.272): full binary tree: #leaves = 1+#branch.