I am trying to prove this statement with strong induction, but I'm a little lost on the inductive step.
Proposition: Let P(n) be the sentence ‘any collection of n coins can be obtained using a combination of 3¢ and 5¢ coins.’
P(n) is true for all integers where n ≥ 14.
Proof:
Prove P(14) is true:
P(14) is true, because 14¢ can be obtained with 3(3¢) and 1(5¢). (9¢ + 5¢ = 14¢)
Prove P(15) is true:
P(15) is true, because 15¢ can be obtained with 5(3¢). (15¢ = 15¢)
Prove P(16) is true:
P(16) is true, because 16¢ can be obtained with 2(3¢) and 2(5¢). (6¢ + 10¢ = 16¢)
Show that for all integers n ≥ 14, if P(i) is true for all integers i from 14 through k, then P(k+1) is also true:
Assume that P(i) is true for all integers from 14 through k.
$k + 1 = [(k + 1) – 3] + 3$
If $k + 1 ≥ 16$, then $(k + 1) – 3 ≥ 14$
I'm not sure where to go from here.
Best Answer
In order to prove it with strong induction you have to assume $n>14$ and that the result is true for every $k$ with $14\le k<n$, after having verified the case $n=14$.
If $n=15$, or $n=16$, you've already done the computations. If $n>16$, then $n-3>13$, so $n-3=3a+5b$ by the (strong) induction hypothesis. Therefore $n=3(a+1)+5b$.