Mathematical induction $3$ and $5$ cent coins

Question

Use mathematical induction to show that for all integers, any price equal or greater than $8$, can be paid for by $3c$ and $5c$ coins.

Answer 1

$n = p*5+q*3$
$n+1 = (p-1)*5+5+1+q*3 = (p-1)*5+(q+2)*3$

Answer 2

This is my first time posting on this website but this is what I think the answer is.What we are trying to prove is that any amount of money can be obtained using 3 cents and 5 centers for number n>=8.

Base step: 8 cents can be made using one 3 cents and one 5 cents therefore its is true.

Inductive step: For all K which is greater then 8 there must a combination of 3 cents and 5 cents used.

First case: if there is 5 cent coin used. Then we have to replace the 5 cent coin with two 3 cent coins, then that will be (k+1) Example: k=8 we have a 5 cent and a 3 cent. For k+1=9 we replace that five cent coin with 2 3 cents so we have 3+3+3=9

Other case: if we have a 5 cent coin used then we know that 3 cent coins replaced it. So we should replace three 3 cents coins with two 5 cents to make up (k+1). Example: k=9 we have 3 3 cent coins. For k+1=10 we replace the 3 3 cents coins with 2 five cent coins. 5+5=10.

I hope this is the answer that you are looking for.

Answer 3

We define a recursive function $\mu = (\mu_1,\mu_2): \{8,9,10,\dots\} \to \Bbb N \times \Bbb N$ as follows:

$\quad \mu(8) \,\;= (1,1)$
$\quad \mu(9) \,\;= (3,0)$
$\quad \mu(10) = (0,2)$

$\quad$ If $\mu(k)$, $\mu(k+1)$, and $\mu(k+2)$ are defined then set $\mu(k+3) = \bigr(\mu_1(k)+1,\, \mu_2(k)\bigr)$

It is easy to prove by induction that

$\tag 1 \mu_1(k) \cdot 3 + \mu_2(k) \cdot 5 = k \quad \text{ for all } k \ge 8$