Mathematical Induction Step

  1. Hi,

    I'm trying to learn mathematical induction for proving inequalities, but there is just one step I cannot get past: finding another inequality that is added to the inductive hypothesis.

    For example, in this problem:

    Prove for all positive integers (n >= 1), prove 3^n + 2 >= 3n.

    I understand the basis step and in general how to do induction, but for some reason, the example says that that after I get the hypothesis, 3^k + 2 >= 3k (for some arbitrary k), it can generate the inequality 2*3^k >= 3 for all k >= 1. Where does this come from? I can follow how it adds this inequality to the hypothesis, but what is this, and how would I go about getting this?

    This isn't just a generic problem by the way: I've looked at many examples, but I can't figure out what this is when dealing with inequalities and induction.
     
  2. jcsd
  3. For your example I would first show: 3n ≥ 3n which is easier.
    You said you can do the basic step. So let's move on to the induction.

    To do the induction we suppose n, then we prove if n is true, n+1 is true.
    So first suppose: 3n ≥ 3n. Then our goal is to show: 3n+1≥3(n+1)

    To do that I would prove the following:
    3n ≥ 3n ⇒ 3+3n ≥ 3(n+1)
    Then i would prove: 3n+1≥3+3n for n>1
    Putting these together: 3n+1≥3+3n≥3(n+1) This step shows our goal!
    Thus by the principle of induction: 3n ≥ 3n for Natural n

    Then you know: 3n ≥ 3n ⇒3n + 2 ≥ 3n or 3n ≥ 3n ⇒3*3*3n =3n+2 ≥ 3n from the properties of inequalities. It's hard to tell which of these you were trying to prove how you wrote it.
     
    Last edited: Nov 2, 2010
  4. Thanks for the reply!

    Sorry: I meant (3^n)+2

    So is there no need for the extra inequality of 2*3^n >= 3? Or am I just missing something?
     
  5. No need for the other inequality, which i think you typed incorrectly.
     
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?