Combinatorial proof other than strong induction

mahjk17

Hi guys, I am wondering if there is a way other than strong induction (I already know how to prove it that way for this problem) for this question, " Show that, for any integer n>=4, there exist non-negative integers a,b such that 5n = 10a + 25b" ??? Is there any other way to prove this other than strong induction? Can I prove this maybe by the binomial theorem ?? Thank you !!!

MarkFL

I would write the equality as:

$$\displaystyle n=2a+5b$$

When n is even, i.e., $$\displaystyle n=2m_1$$ where $$\displaystyle 2\le m_1\in\mathbb Z$$ let b also be even, i.e., $$\displaystyle b=2m_2$$ where $$\displaystyle 0\le m_2\in\mathbb Z$$ so that you have:

$$\displaystyle 2m_1=2a+5\(2m_2$$=2$$a+5m_2$$\)

$$\displaystyle m_1=a+5m_2$$

$$\displaystyle 0\le a=m_1-5m_2$$

$$\displaystyle 5m_2\le m_1$$

We see this is always possible.

When n is odd, i.e., $$\displaystyle n=2m_1+1$$ where $$\displaystyle 2\le m_1\in\mathbb Z$$ let b also be odd, i.e., $$\displaystyle b=2m_2+1$$ where $$\displaystyle 0\le m_2\in\mathbb Z$$ so that you have:

$$\displaystyle 2m_1+1=2a+5\(2m_2+1$$=2$$a+5m_2$$+5\)

$$\displaystyle m_1=a+5m_2+2$$

$$\displaystyle 0\le a=m_1-5m_2-2$$

$$\displaystyle 5m_2+2\le m_1$$

We see this is always possible.

mahjk17

Thank you kind sir !!! What is the name of the proof that you used to do this ? And is it possible to use the binomial theorem to prove this?

MarkFL

I don't think it has a particular name, just a mess of algebra.

I would be willing to bet that someone with some knowledge of number theory could give a much cleaner proof.

I suppose the binomial theorem could be used if both sides of the equation are raised to an integral power, but I think in the end the argument would essentially be the same, although more complicated.

mahjk17

Its clear to me, thank you : )

CRGreathouse

Forum Staff
MarkFL said:
I would be willing to bet that someone with some knowledge of number theory could give a much cleaner proof.
Probably the easiest elementary proof is by induction: 5 = 2*0 + 5*1 and 6 = 2*3 + 5*0, and any number n > 6 can be written as 2 + (n - 2) where n - 2 can be written as a linear combination of 2s and 5s. (I think this is essentially what you wrote?) The shorter advanced proof uses a result of, I believe, Sylvester which shows directly that the answer is (2 - 1) * (5 - 1).