Suppose we had postage stamps worth \(5\) cents and \(3\) cents. Which number of cents can we form using these stamps? In other words, which postage can we pay?
\(11\)?
\(15\)?
\(4\)?
\[\begin{aligned} &CanPay(0) \land \lnot CanPay(1) \land \lnot CanPay(2) \land \\ &CanPay(3) \land \lnot CanPay(4) \land CanPay(5) \land CanPay(6) \\ &\lnot CanPay(7) \land \forall n \in \mathbb{Z}^{\geq 8} CanPay(n) \end{aligned}\]
where the predicate \(CanPay\) with domain \(\mathbb{N}\) is \[CanPay(n) = \exists x \in \mathbb{N} \exists y \in \mathbb{N} ( 5x+3y = n)\]
Proof (idea): First, explicitly give witnesses or general arguments for postages between \(0\) and \(7\). To prove the universal claim, we can use mathematical induction or strong induction.
Approach 1, mathematical induction: if we have stamps that add up to \(n\) cents, need to use them (and others) to give \(n+1\) cents. How do we get \(1\) cent with just \(3\)-cent and \(5\)-cent stamps?
Either take away a \(5\)-cent stamps and add two \(3\)-cent stamps,
or take away three \(3\)-cent stamps and add two \(5\)-cent stamps.
The details of this proof by mathematical induction are making sure we have enough stamps to use one of these approaches.
Approach 2, strong induction: assuming we know how to make postage for all smaller values (greater than or equal to \(8\)), when we need to make \(n+1\) cents, add one \(3\) cent stamp to however we make \((n+1) - 3\) cents.
The details of this proof by strong induction are making sure we stay in the domain of the universal when applying the induction hypothesis.