• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Exercise 1 — Sample Solutions

1. Conjecture: for all n ∈ N, ∑_i=0,1,...,n 2ⁱ⁺¹ = 2ⁿ⁺² - 2.
   Proof by induction:

   • Statement: Let P(n) be the statement: ∑_i=0,1,...,n 2ⁱ⁺¹ = 2ⁿ⁺² - 2.
   • Base Case: ∑_i=0,...,0 2ⁱ⁺¹ = 2¹ = 4 - 2 = 2⁰⁺² - 2, so P(0) holds.
   • Ind. Hyp.: Let n ∈ N and suppose P(n) holds, i.e., ∑_i=0,1,...,n 2ⁱ⁺¹ = 2ⁿ⁺² - 2.
   • Ind. Step: ∑_{i=0,1,...,n+1} 2ⁱ⁺¹ = (∑_i=0,1,...,n 2ⁱ⁺¹) + 2ⁿ⁺² = (2ⁿ⁺² - 2) + 2ⁿ⁺² (by the ind. hyp.) = 2 × 2ⁿ⁺² - 2 = 2ⁿ⁺³ - 2, so P(n+1) holds.
   • Conclusion: By induction, ∀n ∈ N, ∑_i=0,1,...,n 2ⁱ⁺¹ = 2ⁿ⁺² - 2.

2. Conjecture: It is possible to make every amount of postage of 14¢ or more using only 3¢ and 8¢ stamps.
   Proof by induction:

   • Statement: Let P(n) be the statement: ∃t ∈ N, ∃e ∈ N, n = 3t + 8e.
   • Base Case: 14 = 6 + 8 = 3(2) + 8(1), so P(14) holds (by picking t=2, e=1).
   • Ind. Hyp.: Let n ≥ 14 and suppose P(n) holds, i.e., ∃t ∈ N, ∃e ∈ N, n = 3t + 8e.
   • Ind. Step: To prove P(n+1), consider two cases for the value of e that we know to exist from the ind. hyp.
     • Case 1: If e = 0, then n+1 = 3t + 8(0) + 1 so 3t = n ≥ 14 and t ≥ 5. Then, n+1 = 3t + 1 = 3t - 15 + 15 + 1 = 3(t-5) + 16 = 3(t-5) + 8(2), so P(n+1) holds (by picking t'=t-5, e'=2, where we know t' ∈ N because t ≥ 5).
     • Case 2: If e > 0, then n+1 = 3t + 8e + 1 = 3t + 8(e-1) + 9 = 3(t+3) + 8(e-1), so P(n+1) holds (by picking t'=t+3, e'=e-1, where we know e' ∈ N because e ≥ 1).
     In either case, P(n+1) holds.
   • Conclusion: By induction, ∀n ≥ 14, P(n), i.e.. it is possible to make every amount of postage of 14¢ or more using only 3¢ and 8¢ stamps.