Question

Which amounts of money can be formed using just two-dollar bills and five-dollar bills? Prove your answer using strong induction.

Short answer

All amounts can be formed except $1 and $3.

Step-by-step solution

Describe given information

It is given that there are two-dollar bills and five-dollar bills, out of which amounts of money has to be formed.

Determine amount of money that can be formed using two-dollar bills and five-dollar bills

Using two-dollar bills and five-dollar bills, the following amounts of money can be formed:

$$\begin{gathered} 2=2 \\ 4=2+2 \\ 5=5 \\ 6=2+2+2 \end{gathered}$$

$7=5+2$

By considering all the combinations, the gaps in the above list cannot be filled.

That is $1 and $3 cannot be formed.

Claim: All amount of money greater than or equal to $5 can be formed using two-dollar bills and five-dollar bills.

Proof using strong induction

Let$P\left(n\right):$n dollars can be formed using just two-dollar bills and five-dollar bills.

To prove: The statement is true for all $n\ge 5$.

The basis step: The statement is true for$n=5,6,7$ (as done in Step 1)

Inductive hypothesis: Assume that the statement$P\left(j\right)$ is true for all j with $5\le j\le k$, where k is a fixed integer greater than or equal to 6.

To show: The statement$P(k+1)$ is true.

Proof: Since $k-1\ge 5$, so$P(k-1)$ is true that is$k-1$ dollars.

By putting one more two-dollar bill,$k+1$ dollars can be formed.

This implies$P(k+1)$ is true.

Hence, the statement is true. All amounts can be formed except $1 and $3.