$3$ and $5 $cent coins

Question

Prove that any amount of more that $7$ cents can be represented by $3$ and $5$ cent coins. (Assume $3$ cent coins exist.)

Let P(n) be true if we can find $n$ cents with $3$ and $5$ cent coins.

My basis step is:

$P(8)$ is true since $3 + 5 = 8$

Would this be correct?

As for the inductive step, I'm not sure how to show it.

I've looked around online and it seems to be:

$P(k) = 8 ≤ k ≤ n$

How would I prove this to be true?

Answer 1

Observe that $8 = 3+5$, $10 = 2\cdot 5$, and $9 = 3\cdot 3$.This means $P(8)$, $P(9)$ and $P(10)$ are true. Assume $P(k)$ is true for $10 \leq k < n$, we prove $P(n)$ is true: Observe that $n = (n-3) + 3$, and $P(n-3)$ is true so $n-3 = 3m+5p \to n = 3+3m+5p = 3(m+1) + 5p$

Answer 2

First, figure out how to make change. Then worry about finding a proof that your method of making change works.

Answer 3

A hint: if you know a representation for $n$ then you need to find a way to use it in order to find a representation for $n + 1$.

Just replace 5 by two 3s, if there are no 5s then replace three 3s (prove that they exist) by two 5s.

Answer 4

This can be done by strong induction (as $8 \leq k \leq n$ seems to suggest) or by multiple base cases (as another answer suggests) or by a single base case and weak induction.

For weak induction, starting with your base case ($3 + 5 = 8$), you then show that if you can add up coins to a total of $n,$ you can also add up coins to a total of $n+1.$

To do that, you must show that you can take a subset of the coins and replace them with other coins whose sum is $1$ greater than the coins you removed. You will need more than one way to do this, because if you repeat the same replacement over and over you will eventually take away too many coins of one kind and will be unable to repeat that step. So there must be at least two different ways to increase the total by $1$ by exchanging some coins. Moreover, you have to show that you can always find at least one set of coins totaling $m$ that can be replaced by coins totaling $m+1.$

That last fact becomes part of what you need to prove in both the base and inductive steps. That is, the $P(n)$ you prove in the end is not just, "We can add up $3$- and $5$-cent coins to total $n,$" but rather, "We can add up $3$- and $5$-cent coins to total $n,$ and the sum will either contain [a list of coins] or [another list of coins]."

To figure out what those lists of coins are that you replace, and what you replace them with, try actually working out the sums for $8,9,10,$ and maybe a few more consecutive numbers, and see what the difference is in the list of coins each time you increase the sum by one (that is, by how much did you decrease one kind of coin, and by how much did you increase the other).

Answer 5

proof by induction

p(8): 3.(1)+5.(1)=8 holds

Assume p(k) holds => 3.a + 5.b = k

we must prove that p(k+1) holds.

p(k+1): 3x+5y = k+1=> 3x+5y = 3a+5b+1=> 3(x-a) + 5(y-a)

thus suffices to prove that 3z+5ω =1 has an integer solution. That is true because gcd(3,5)=1 | 1 (1 divides 1)

Calculating gcd(3,5) gives: 5 = 1*3 + 2

3 = 1*2 + 1

2 = 2*1 + 0

Then applying the Extended Euclidean Algorithm:

1 = (1 * 3) + (-1 * 2) = (-1 * 5) + (2 * 3)=> z0=2, ω0=-1 => 3.2+5.(-1) = 1=> p(k+1) holds as well