CompleteInduction-Example

Proof. We prove by complete induction that any amount of at least 8 cents can be made by using 3 cents and 5 cents. The induction hypothesis, P(n) will be:

 there is a collection of coins whose value is n + 8 cents.

"simply follow the template given in the previous post about complete induction."
"very similar to the Postage question we did during the lecture"

BaseCase: P(0) is true because a 3 cent coin together with a 5 cents coin makes 8 cents

Inductive Step: We assume P(m) holds for all m <= n, and prove that P(n+1) holds. There are two different cases; we prove by cases

Case 1. (n+1=1), then (n+1)+8 = 9 cents, we can make 9 cents by using 3 x 3 cents = 9 cents
Case 2. (n+1=2), then (n+1)+8 = 10 cents, we can make 9 cents by using 2 x 5 cents = 10 cents

Case 3. (n+1 >= 3), then 0 <= n - 2 <= n, so by the complete induction hypothesis, for n-2 cents amount can be made. Now by adding a 3 cents coin; n-2 + 3 = n+1 can be made

Conclude that P(n), any amount of 8 cents or more can be made out of 3 cents and 5 cents coins, holds for every positive natural integers, n.