# How to prove by induction the following problem? [closed]

Prove by induction that any amount of postage of at least 24 cents can be made up with only 4-cent and 9-cent stamps.

## closed as off-topic by qbert, mrp, Juniven, Chris Godsil, NamasteMay 5 '17 at 13:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – qbert, mrp, Juniven, Chris Godsil, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

• I believe you can at least get the base case! – qbert May 5 '17 at 0:42

We have a proposition $$P_n:\exists x,y\in\mathbb{N}\quad\text{such that}\quad n=4x+9y,\quad n\geq24$$

First we must show its true for the base case $n=24:$

$24=4\cdot 6\implies$ $P_n$ holds

Assume $P_n$ is true, now we must prove $P_{n+1}$ is true.

$(n+1) = 4x+9y+1\quad$ There are some cases to consider.

$(1): x\geq 2\implies n+1= 4(x-2)+9y+8+1=4(x-2)+9(y+1)$

$(2):x=1\implies y\geq 3\implies n+1=4+9y+1 =5+9(y-3)+27=4\cdot8+9(y-3)$

$(3):x=0\implies y\geq 4 \implies n+1=9y+1= 9(y-4)+36=9(y-4)+4\cdot 9$

In all cases we have shown that $n+1$ can be written in the required form, hence our statement $P_n$ holds $\forall n\in\mathbb{N_{n\geq 24}}$

24=4+4+4+4+4+4

25=9+4+4+4+4

26=9+9+4+4

27=9+9+9

28=24+4, 29=25+4, 30=26+4, ...

Statement to be proven: $\forall n\in \Bbb N, \exists \{k,\ell\} : n+23 = 4k+9\ell$

Equivalent statement: $$\forall m\in \Bbb N, \left\{ \begin{array}{c} \exists \{k_0,\ell_0\} : 4m+20+0 = 4k_0+9\ell_0\\ \exists \{k_1,\ell_1\} : 4m+21+1 = 4k_1+9\ell_1\\ \exists \{k_2,\ell_2\} : 4m+22+2 = 4k_2+9\ell_2\\ \exists \{k_3,\ell_3\} : 4m+23+3 = 4k_3+9\ell_3 \end{array} \right.$$

We will prove the equivalent statement (ES) by induction on $m$.

Basis: when $m=1$, ES(1) reads $$\left\{ \begin{array}{c} \exists \{k_0,\ell_0\} : 24 = 4k_0+9\ell_0\\ \exists \{k_1,\ell_1\} : 25 = 4k_1+9\ell_1\\ \exists \{k_2,\ell_2\} : 26 = 4k_2+9\ell_2\\ \exists \{k_3,\ell_3\} : 27 = 4k_3+9\ell_3 \end{array} \right.$$ with all the $k_i$ and $\ell_i$ non-negative integers, which is demonstrated by $$\{ k_0 = k_1=k_2=k_3 = 6, \ell_0 = 0, \ell_1 = 1, \ell_2 = 2, \ell_3 = 3\}$$

Induction: assume ES is true for some $m$ using some set of $k^{(m)}_i,\ell^{(m)}_i$. . Then ES$(m+1)$ is shown to be true by using

$$\begin{array}{cccc} k_0 = k^{(m)}_0 +1& k_1 = k^{(m)}_1+1&k_2 = k^{(m)}_2+1&k_3 = k^{(m)}_3+1\\ \ell_0 = \ell^{(m)}_0&\ell_1 = \ell^{(m)}_1&\ell_2 = \ell^{(m)}_2&\ell_3 = \ell^{(m)}_3& \end{array}$$

Thus induction is established, and (ES) is true for all natural $m$, so the original statement is true for all integer $m\geq 24$.