Induction: Prove that any integer postage greater than 34 cents can be formed using only 5-cent and 9-cent stamps

Question

How can I prove by induction that for all n in the set of positive natural numbers and $n>34$, there exists a k and s in the set of all positive natural numbers, such that $n=5k+9s$. Please forgive me for the notation if it is wrong.

This is my proof attempt:

Base case;$ n =35$ $A(n) = 5k + 9s$ $A(35) = 5(7) + 9(0) = 35$

Assume $A(n)$ where $n$ belongs to the set of all positive natural numbers and $n>34$

Now for $A(n+1) = 5k+9s = 5(0) + 9(4) = 36$, so there exists a $k,s$ belonging to set of all possible natural numbers for which $A(n+1)$ holds.

Thus $A(n)$ implies $A(n+1)$, and for all n belonging to the set of all positive natural numbers and $n>34$ it holds there exists a $k$ and $s$ in the set of all positive natural numbers, such that $n=5k+9s$.

I know this is not accurate, but after consulting my provided reading material, it still remained unclear. Could you tell me whats wrong with my proof and how to fix it.

Also if could point me towards an intuitive explanation of induction I would greatly appreciate it.

Thanks!

Answer 1

Base case: $n =35 A(n) = 5k + 9s A(35) = 5(7) + 9(0) = 35$

so far so good:

Assume $A(n)$ where $n$ belongs to the set of all positive natural numbers and $n>34$

Okay, I think I would be explicit and write out the proposition, rather and saying $A(n)$.

But, it falls apart after that.

We need to show that if $n = 5p+9q$ then $n+1 = 5r+9s$ (with $r$ and $s$ as positive integers.

Notice that:

$-5(7) + 9(4) = 1\\ 5(2) - (9) = 1$

In order for our proposition to be true we need either $q\ge1$ or $p\ge7$

We could try to make a clever argument to show why this is true, but I think it is easier to expand the base case.

$36 = 9\cdot 4, 37 = 9\cdot 3 + 2\cdot 5, 38 = 9\cdot 2 + 4\cdot 5, 39 = 9\cdot 1 + 6\cdot 5.$

Assume:

$n = 5p+9q\\ n+5 = 5(p+1) + 9q$

Answer 2

You should consider that 35, 36, 37, 38 and 39 are all base cases.

$$ 35 = 5\times 7 + 9\times 0 \\ 36 = 5\times 0 + 9\times 4 \\ 37 = 5\times 2 + 9\times 3 \\ 38 = 5\times 4 + 9\times 2 \\ 39 = 5\times 6 + 9\times 1 \\ $$

This is because the smallest step you can take with 5- or 9-cent stamps is 5 (just tacking another 5-cent stamp on the envelope). After treating these cases, it is easy to go from $n \rightarrow n+5 $. The conclusion follows.

Answer 3

You don't need induction to prove this (or maybe implicitly). Actually all numbers from $32$ can be obtained as a sum of $5$s and $9$s.

To see it, classify natural numbers modulo $5$: clearly

• all numbers congruent to $0\bmod5$ can be obtained;
• all numbers congruent to $4$ from $9$ can be obtained;
• all numbers congruent to $3$ from $18$ can be obtained;
• all numbers congruent to $2$ from $27$ can be obtained;
• all numbers congruent to $1$ from $36$ can be obtained.

Hence all numbers from $35$ can be obtained.

There remains the cases of $32$, $33$ and $34$, which you can manage individually: $$32=5+3\times 9,\quad 33=3\times5+2\times 9,\quad 34=5\times5+9. $$

Answer 4

You have to use a "no-longer a 98 lb. weakling" induction. Just kidding. (But really, strong induction is nothing to be afraid of).

The trick is, you'll need two alternative induction steps:

Proposition: $P(n): $ For any $n \ge 35$ there are $a_n,b_n \in \mathbb N + \{0\}$ so that $n = 5a_n + b_n$.

Base case: $n = 35$

Induction step 1: If true for $n = k$ and $b_k > 0$ then $P(n)$ is true for $n = k+1$

Induction step 2: If true for $n = k; b_k = 0$ and $k \ge 35$ the $P(n)$ is true for $n = k+1$.

As one or the other of the conditions of step 1) or 2) must be true, induction legitimately follows.

Proof:

Base case: $n = 35; a_n = 7; b_n = 0$ and $ 35 = 7*5 + 0$.

Induction step 1: $k = 5a_n + 9b_n; b_n>0$ then $k +1 = 4(a_n + 2) + 9(b_n - 1)$.

Induction step 2: $k = 5a_n + 9*0; k \ge 35$ then $a_n \ge 7$ and $k+1 = 5(a_n- 7) + 4*9$.

===

Actually we can prove this for $n \ge 32$ as $32 = 1*5 + 3*9$ and $P(n)$ for $n = 33, 34,35$ will follow from induction step 1).

It's not valid for $n = 31$ as $a_{32}=1; b_{32}=3$ so either $1 = a_{32}=a_{31}+2\implies a_{31} < 0$ or $3 = b_{32} = b_{31} + 4 \implies b_{31} < 0$.

===

These are all variations of Euclid algorithm that there exist integers $a,b$ where $n*\gcd(5,9) = n = 5a + 9b$. And $ 1 = 2*5 - 1*9 = -7*5 + 4*9$. For any $m = 5a + 9b$ we can also have $m = 5(a \pm 9k) + 9(b \mp 5k)$.