Use the principle of strong mathematical induction to prove that if $n\in\mathbb N, n\geq12$ , then there exist non-negative integers $x$ and $y$ such that $n=4x+5y$.
Asked
Active
Viewed 7,027 times
1
-
1I suggest this should be closed as a duplicate. All you have to do is search for "postage stamp". – Rick Decker Nov 15 '12 at 15:47
2 Answers
3
Let's suppopse $n=4x+5y$, then we have $$n+1=4(x-1)+5(y+1) = 4(x+4)+5(y-3) $$ The only problematic case for these is when both $x<1$ and $y<3$, i.e. for $n\le 10$.
Start: $12=3\cdot 4+0\cdot 5$.
Berci
- 90,745
-
Dang, Berci. Beat me by 3 seconds. Still, we've presented slightly different solutions: yours is more elegant, mine is more general. – Rick Decker Nov 15 '12 at 15:37
3
Start with $13 = 4\cdot2+5\cdot1, 14 = 4\cdot1+5\cdot2,15 = 4\cdot0+5\cdot3,16 = 4\cdot6+5\cdot0$ as your base case. For the inductive step, let $n$ be a natural number greater than $16$ and assume that all numbers $13\le k < n$ may be written as $k=4x+5y$ for nonnegative $x, y$. Then by the inductive hypothesis $n-4$ can be written as $4a+5b$ and so $n=4(a+1)+5b$, thus showing that $n$ can be expressed in the desired form. Done.
Rick Decker
- 8,718