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$.
Strong mathematical induction to prove $n=4x+5y$
1
$\begingroup$
discrete-mathematics
-
1I suggest this should be closed as a duplicate. All you have to do is search for "postage stamp". – 2012-11-15
2 Answers
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.
2
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$.
-
0Dang, Berci. Beat me by 3 seconds. Still, we've presented slightly different solutions: yours is more elegant, mine is more general. – 2012-11-15