Homework Help: Inductive Proof (+linear equation in four variables)

1. Sep 21, 2011

sweetreason

1. The problem statement, all variables and given/known data

I'm trying to prove by induction that $\forall n \geq 5, \exists m_1, m_2 \in \mathbb{N}$ such that $n = 2m_1 +3m_2.$

2. Relevant equations

(none, really)

3. The attempt at a solution

I've done the base case, and the inductive step boils down to showing that $\exists m_1 \prime m_2 \prime$ such that $2m_1 +3m_2 +1 = 2m_1 \prime +3m_2 \prime$. Maybe I'm forgetting something from grade school algebra, but I have no idea how to solve for $m_1 \prime, m_2 \prime$. I've plugged it into wolfram alpha [http://www.wolframalpha.com/input/?i=2*x_1+3*x_2+++1+=+2*y_1+++3*y_2] and got solutions (all I care about is the case n =1 for the integer solutions wolfram gives) but I want to know how to arrive there.

2. Sep 21, 2011

kru_

Is this really something that you need induction for?

There are really only two cases for any n. Either 2|n, or it does not. Both cases are pretty easy to see what m1 and m2 need to be for any given n.

I'll think about how to proceed with an inductive proof for a little while (until I give up, at least). But, if it were me, I'd choose a proof by cases.

3. Sep 21, 2011

sweetreason

I managed to prove this using induction, actually. It's a lot easier if you prove an additional base case (n=6) and then prove it for n >=7. I am still curious as to how to solve for those variables though.

4. Sep 21, 2011

sweetreason

In case you're curious, for the inductive step just add one to both sides of your induction hypothesis, then factor out 2's to obtain the desired expression.