Combinatorial proof other than strong induction

May 2012
60
0
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 !!!
 
Jul 2010
12,211
522
St. Augustine, FL., U.S.A.'s oldest city
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.
 
May 2012
60
0
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?
 
Jul 2010
12,211
522
St. Augustine, FL., U.S.A.'s oldest city
I don't think it has a particular name, just a mess of algebra. :D

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.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
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).