Inductive Proof (+linear equation in four variables)

[sweetreason]

Homework Statement

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.

Homework Equations

(none, really)

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.

 

[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.

 

[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.

 

[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.