Homework Week 7

Official assignment: 3, 4, 5, 6, 11, 15, 25, 37.

Problem 3

Postage using 3-cent and 5-cent stamps. Show the relevant postage amounts can be formed. The worked notes used base cases 8, 9, and 10 and then added a 3-cent stamp.

Problem 4

Postage using 4-cent and 7-cent stamps. Show the relevant postage amounts can be formed. The worked notes used base cases 18, 19, 20, and 21 and then added a 4-cent stamp.

Problems 5 and 6

Exact text not pasted in chat. Listed in the official Week 7 assignment.

Problem 11

Nim variation. Positions congruent to \(1 \pmod 4\) are losing positions.

Problem 15

Exact text not pasted in chat. Listed in the official Week 7 assignment.

Problem 25

Analyze what conclusions can be drawn from different induction hypotheses:

1. \(P(1)\) true and \(P(n)\to P(n+2)\).
   
2. \(P(1),P(2)\) true and \(P(n),P(n+1)\to P(n+2)\).
   
3. \(P(1)\) true and \(P(n)\to P(2n)\).
   
4. \(P(1)\) true and \(P(n)\to P(n+1)\).

Problem 37

Prove uniqueness of the quotient \(q\) and remainder \(r\) in the division algorithm.

Official assignment: 1, 3, 5, 7, 26, 27, 45.

Problems 1 and 3

Exact text not pasted in chat. Listed in the official Week 7 assignment.

Problem 5

Determine whether each recursive definition is valid and, where possible, find a formula. Subparts referenced in the worked notes: (a), (b), (c), (d), (e).

Problem 7

Find recursive definitions for sequences. Subparts in the worked notes:

1. \(a_1=6\), \(a_n=a_{n-1}+6\).
   
2. \(a_1=3\), \(a_n=a_{n-1}+2\).
   
3. \(a_1=10\), \(a_n=10a_{n-1}\).
   
4. \(a_1=5\), \(a_n=a_{n-1}\).

Problem 26

Use structural induction to show every element of recursively defined set \(S\) is congruent to \(1 \pmod 4\), where the worked notes use rules involving \(3n+2\) and \(n^2\).

Problem 27

Use structural induction to show every element of recursively defined set \(S\) is congruent to \(5 \pmod {10}\), where the worked notes use rules involving \(3n\) and \(n^2\).

Problem 45

Use structural induction on full binary trees to prove:

\[ n(T)\ge 2h(T)+1. \]