Proof that every integer > 3 cash amount can be payed by arbitrary number of coins of value 2 and 5

Question

This question is about the following word problem:

Show that every integer cash amount $k$ greater than 3 can be payed by $m$ coins of value 2 and $n$ coins of value 5.

where: $ m, n \in \mathbb{N}_0, $

I tried to prove this by induction.

So for base case $ k =4 $

We get that $4 = 2 \cdot 2 + 5 \cdot 0$

(Basically we need $2$ coins of value $2$ and $0$ coins of value $5$)

I tried working with other base cases but I was unable to find a way to prove: $$P(k) \implies P(k+1)$$

Is induction the right way to prove this? Or should I try to prove it by other techniques?

Answer 1

Base cases: $n=4,5$: $$4= 2\cdot 2+0\cdot 5$$ $$5= 0\cdot 2+1\cdot 5$$

Induction step: $n\to n+2$:

$$n= 2a+5b \Longrightarrow n+2 = 2(a+1)+5b$$

Answer 2

Induction is fine, but you may want to start by showing $P(4)$ and $P(5)$ explicitly and then using $P(n)\implies P(n+2)$. If that confuses you, let $Q(n):=P(2n)\land P(2n+1)$, show $Q(2)$ and $Q(n)\implies Q(n+1)$.

Answer 3

Let $n \in \mathbb N_0$ with $n \ge 4$.

Write $n-4=2q+r$ with $0 \le r \le 1$.

If $r=0$, we have $n=(q+2)\cdot 2 + 0 \cdot 5$.

If $r=1$, we have $n=q\cdot 2 + 1 \cdot 5$.

Answer 4

An even sum can be paid with $n$ coins of value $5$ (where $n$ is $0$ or even) and $m$ coins of value $2$.

An odd sum can be paid with $n$ coins of value $5$ (where $n$ is odd) and $m$ coins of value $2$.