This question already has an answer here:

Largest integer that can’t be represented as a non-negative linear combination of m,n=mn−m−nm, n = mn – m – n? Why?

5 answers

Prove that every natural number n⩾12n\geqslant 12 can be written as a linear combination of 44 and 55 with non negative integer coefficients.

I proceeded by induction.

For n=12n=12 we have 12=3\cdot 4 +0\cdot 512=3\cdot 4 +0\cdot 5

Let n>12n>12

Suppose that the hypothesis is valid for every k\in \mathbb{N}k\in \mathbb{N} with 12

\begin{align} k+1 &= x\cdot4+y\cdot5 + 1 \\

&= (x-1)\cdot4 + y\cdot5 +4 +1 \\

&= (x-1)\cdot4 + y\cdot5 +5 \\

&= (x-1)\cdot4 + (y+1)\cdot5\\

\end{align}\begin{align} k+1 &= x\cdot4+y\cdot5 + 1 \\

&= (x-1)\cdot4 + y\cdot5 +4 +1 \\

&= (x-1)\cdot4 + y\cdot5 +5 \\

&= (x-1)\cdot4 + (y+1)\cdot5\\

\end{align}

If x = 0x = 0 then k= y\cdot5k= y\cdot5, with \mathbf{y\ge3}\mathbf{y\ge3}, since n\ge12n\ge12. Hence \begin{align} k+1 &= y\cdot5 +1 \\

&= (y-3)\cdot5 +15+1 \\

&= (y-3)\cdot5 +16 \\

&= (y-3)\cdot5 + 4\cdot4\\

\end{align}\begin{align} k+1 &= y\cdot5 +1 \\

&= (y-3)\cdot5 +15+1 \\

&= (y-3)\cdot5 +16 \\

&= (y-3)\cdot5 + 4\cdot4\\

\end{align}

So we have proven that k+1k+1 can be written in the form of x’\cdot4+y’\cdot5x’\cdot4+y’\cdot5, with x’,y’\ge0x’,y’\ge0

2

This is an elegant proof. Not only does it use induction, as required by OP, but unlike my solution it does not require any more manual computation than necessary. @capo, you should consider switching to this as your answer, if you can.

– Larry B.

yesterday

it’s indeed a very nice elegant solution..good job..thank you!

– capo

yesterday

It’s the right idea, but you can do it without induction.

We’ll take your idea of doing the first dozen computations, so we need to prove for k > 24k > 24. Let 0\leq a<120\leq a<12 be such that a \equiv k \mod 12a \equiv k \mod 12, so k = (12 + a) + 12\cdot jk = (12 + a) + 12\cdot j. We know that 12\cdot j = 4\cdot (3 \cdot j)12\cdot j = 4\cdot (3 \cdot j), and we have the manual computations for 12 + a = 4\cdot x + 5 \cdot y12 + a = 4\cdot x + 5 \cdot y, thus k = 4\cdot (x + j\cdot 3) + 5\cdot yk = 4\cdot (x + j\cdot 3) + 5\cdot y i think a is a=amod12a=amod12 i dont understand the use of kk – capo 2 days ago We are defining aa to be such that a \equiv k \mod 12a \equiv k \mod 12. For instance, if k = 55k = 55, a = 7a = 7. – Larry B. 2 days ago oh isee then..is it possible to prove this by induction? – capo 2 days ago @capo you can take a look at my answer on how to prove this by induction. – Thanassis 2 days ago