Suppose I have an unlimited supply of $k$th and $(k+1)$th cents where $k \in \mathbb{N}$, then I can always pay integer bills starting from $k(k-1)$ cents using only the two types of coins I have. Let this statement be $P(k)$. So,
$P(1):$ I have coins of $1$ and $2$ cents, then I can pay any bill starting from $1(1-1)=0$ cents. (This is true because it does not require any coins).
$P(2):$ I have coins of $2$ and $3$ cents, then I can pay any bill starting from $2(2-1)=2$ cents.
$P(5):$ I have coins of $5$ and $6$ cents, then I can pay any bill starting from $5(5-1)=20$ cents.
Now $P(k)$ seems to hold fine for some arbitrarily chosen positive integer, but I would like to validate this statement using the principle of induction:
Base case:
$P(1)$ holds. (See from above)
Induction on $k$:
Assume $P(i)$ holds for $1\leq i \leq k$. Using this assumption I have to prove $P(k+1)$ holds. I am stuck here, how should I approach it? Thanks in advance.
Asked
Active
Viewed 375 times
0
Terrarium
- 145
- 5
-
2Do you need to use induction? Even with strong induction, I don't think you'll have an easy time using $P(i)$'s to prove $P(k+1)$. – A.J. Dec 24 '20 at 07:05
-
@A.J. Are there any other ways to prove it? – Terrarium Dec 24 '20 at 07:08
-
Perhaps fix $k$ first, then use (strong) induction on the amount on the bill $n \ge k(k-1)$. – player3236 Dec 24 '20 at 07:18
1 Answers
1
Here's an outline of an induction proof for a fixed $k$ :
$k(k-1)$ cents can be paid with $(k-1)$ k-cent coins.
$k(k-1) +1$ cents can be paid with $(k-2)$ k¢ coins plus $1$ k+1 cent coin.
$k(k-1) +2$ cents can be paid with $(k-3)$ k¢ coins plus $2$ k+1 cent coins.
$$\vdots$$
$k(k-1) + k-2$ cents can be paid with $1$ k¢ coin plus $(k-2)$ k+1¢ coins.
$k(k-1) + k-1$ cents can be paid with $(k-1)$ k+1 cents coins.
i.e. $(k^2-1)$ cents can be paid with $(k-1)$ k+1-cent coins.
But then $k^2$ cents can be paid with $k$ k-cent coins, and from there the cycle repeats.
A.J.
- 3,892