1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 21, 2011 #1
    1. The problem statement, all variables and given/known data

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

    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 [itex] \exists m_1 \prime m_2 \prime [/itex] such that [itex]2m_1 +3m_2 +1 = 2m_1 \prime +3m_2 \prime [/itex]. Maybe I'm forgetting something from grade school algebra, but I have no idea how to solve for [itex] m_1 \prime, m_2 \prime [/itex]. 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. jcsd
  3. Sep 21, 2011 #2
    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.
  4. Sep 21, 2011 #3
    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.
  5. Sep 21, 2011 #4
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook