Subjects algebra

Postage Induction

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Use the AI math solver

1. **Problem Statement:** We want to prove that every amount of postage of at least 12 cents can be formed using only 4-cent and 5-cent stamps. 2. **Base Cases:** Check the amounts 12, 13, 14, and 15 cents: - 12 = 3 \times 4 - 13 = 2 \times 4 + 1 \times 5 - 14 = 1 \times 4 + 2 \times 5 - 15 = 3 \times 5 All these can be formed using 4-cent and 5-cent stamps. 3. **Inductive Hypothesis:** Assume that for some integer $k \geq 15$, every amount of postage from 12 up to $k$ cents can be formed using 4-cent and 5-cent stamps. 4. **Inductive Step:** We need to prove that postage of $k+1$ cents can also be formed. Since $k+1 - 4 = k - 3$ and $k - 3 \geq 12$ (because $k \geq 15$), by the inductive hypothesis, postage of $k - 3$ cents can be formed. Adding one more 4-cent stamp to that amount gives $k+1$ cents. 5. **Conclusion:** By mathematical induction, every amount of postage of at least 12 cents can be formed using 4-cent and 5-cent stamps.