1

The following statements can be easily proved by induction:
If I have coins of $3$ and $5$ cents (then difference, $d=5-3=2)$, then I can pay any bill starting from $(3-1)(3+d-1)=8$ cents.
If I have coins of $5$ and $9$ cents (then $d=4)$, then I can pay any bill starting from $(5-1)(5+d-1)=32$ cents.

I did some trial and errors and guessed the following:
$\forall k,d\in \mathbb{Z^+}$, if you have coins of $k$th and $(k+d)$th cents given that both $k$ and $(k+d)$ are co-prime, then you can pay any bill starting from $(k-1)(k+d-1)$ cents.
This seems to work out for most of the cases I have tried, but I would like to validate this statement by using proof by induction.
Base case:
Let $k=1, d=1$, then I have coins of $1$ and $2$ cents. I can pay any bill starting from $(k-1)(k+d-1)=(1-1)(1+1-1)=0$ cents (since it does not require any coins). Similarly, I can pay bills of $1, 2, 3, ... n \in \mathbb{Z^+}$ cents assuming that I have an unlimited supply of cents.
Induction on $k$:
Assume that $P(k,d)$ denotes the statement: I have unlimited coins of $k, (k+d)$ cents.
Then I can pay bills starting from $(k-1)(k+d-1)$. In other words, $P(k,d)\implies(k-1)(k+d-1)$
Now I have to prove $P(k+1, d)\implies(k)(k+d)$. I am stuck here, how should I approach? Similarly I have to do induction on $d$, but I cannot seem to find a way to solve this problem. Thanks in advance.

Terrarium
  • 145
  • 5
  • The issue is that k+1,d is not necessarily coprime. The issue of the numbers being coprime will make this problem really challenging in terms of induction. It may also help to try rephrasing the problem into a more mathematical language. Let $P(u,k,d)$ be the statement $\forall z\in\mathbb{N}^{\ge u}(\exists x,y\in\mathbb{N} (xk+y(k+d)=z))$. Then your problems statement is $\forall k,d\in\mathbb{N}^{+} (k,d\text{ coprime} \Rightarrow (P((k-1)(k+d-1),k,d)\wedge \forall u\in\mathbb{N} (P(u,k,d) \Rightarrow u \ge (k-1)(k+d-1))))$ – aefrrs Dec 23 '20 at 21:02

0 Answers0