$3$ and $5 $cent coins 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?
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 &lt; 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$
proof by induction
p(8): 3.(1)+5.(1)=8 holds
Assume p(k) holds =&gt; 3.a + 5.b = k
we must prove that p(k+1) holds.
p(k+1): 3x+5y = k+1=&gt; 3x+5y = 3a+5b+1=&gt; 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)=&gt; z0=2, ω0=-1 =&gt; 3.2+5.(-1) = 1=&gt; p(k+1) holds as well