Results 1 to 8 of 8

Thread: Mathematical Induction [inequalities]

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    49

    Mathematical Induction [inequalities]

    Im not good at induction involving inequalities; can someone help me prove by mathematical induction:

    1) 2^n - n^2 > 0 where n>4

    2) n^2 - 3n + 2
    ≥ 0

    3) 4^n - 1 - 7n
    ≥ 0 where n ≥2

    thanks

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Like a stone-audioslave ADARSH's Avatar
    Joined
    Aug 2008
    From
    India
    Posts
    726
    Thanks
    2
    Quote Originally Posted by noobonastick View Post
    Im not good at induction involving inequalities; can someone help me prove by mathematical induction:

    1) 2^n - n^2 > 0 where n>4

    2) n^2 - 3n + 2
    ≥ 0

    3) 4^n - 1 - 7n
    ≥ 0 where n ≥2

    thanks

    All the questions are almost same try them after seeing this

    P(n) :2^n - n^2 >0 When n>4

    First step:

    $\displaystyle P(5) = 2^5 - 5^2 = 32 - 25 = 7 $

    Now 7 >0 hence its correct for n = 5

    Assumption : P(k) is correct

    ie; $\displaystyle 2^k - k^2 >0 $

    Hence$\displaystyle 2^k> k^2 $

    Proof for P(k+1) using assumption:

    $\displaystyle 2^{k+1}- (k+1)^2 = 2 \times 2^k - k^2 -1-2k $


    since $\displaystyle 2^k > k^2 $
    Hence

    $\displaystyle 2 \times 2^k - k^2 -1-2k > 2 \times k^2 - k^2 -1-2k$

    $\displaystyle 2 \times 2^k - k^2 -1-2k > k^2 -1-2k$

    $\displaystyle 2 \times 2^k - k^2 -1-2k > (k+1)^2 $

    But since (k+1)^2 is always a positive number (greater than 16 atleast ) thus proved that its correct for k+1 hence through the principle of mathematical induction this is proved
    Last edited by ADARSH; Mar 17th 2009 at 02:04 AM. Reason: greater than 25 is not really true if n is not an integer
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    49
    I can't seem to get the answer to the last question.

    I have to prove 21k - 4 > 0 ... but how do I do that.

    Do I state that if I sub in k ≥ 2, then 21k - 4> 0?
    Last edited by noobonastick; Mar 17th 2009 at 02:11 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Like a stone-audioslave ADARSH's Avatar
    Joined
    Aug 2008
    From
    India
    Posts
    726
    Thanks
    2
    Quote Originally Posted by noobonastick View Post
    I can't seem to get the answer to the last question.

    I have to prove 21k - 4 > 0 ... but how do I do that.

    Do I state that if I sub in k ≥ 2, then 21k - 4> 0?
    Yes that is a good reason
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    1
    I know the rules state create a new thread for each problem, but this isn't really a new problem. Rather, it's a question regarding the solution posted, as I'm unsure as well about the application of induction to inequalities.

    Reading the Assumption step, I'm not sure how that would work if p(n) = 2^n > n^2, for n>4. Would it essentially be the opposite to what was posted, becoming "hence: 2^n - n^2 > 0" ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    $\displaystyle 2^n-n^2\ >0$

    is the same as

    $\displaystyle 2^n>n^2$

    Here is another way to prove it by induction..

    P(k)

    $\displaystyle 2^k>k^2$ for k>4

    P(k+1)

    Try to prove that

    $\displaystyle 2^k>k^2$

    causes

    $\displaystyle 2^{k+1}>(k+1)^2$

    Proof

    $\displaystyle 2^{k+1}>(k+1)^2$ ?

    $\displaystyle (2)2^k>k^2+2k+1$ ?

    $\displaystyle 2^k+2^k>k^2+2k+1$ ?

    If k>4, then $\displaystyle 2^k>2k+1$

    hence, if $\displaystyle 2^k>k^2$

    then

    $\displaystyle 2^k+2^k>k^2+2k+1$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    For the 3rd..

    P(k)

    $\displaystyle 4^k-1-7k\ \ge\ 0,\ k\ \ge\ 2$ ?

    $\displaystyle 4^k\ \ge\ 7k+1$ ?

    P(k+1)

    Does $\displaystyle 4^k\ \ge\ 7k+1$ cause

    $\displaystyle 4^{k+1}\ \ge\ 7(k+1)+1$ ?

    Proof

    $\displaystyle 4^{k+1}\ \ge\ 7(k+1)+1$ ?

    $\displaystyle (4)4^k\ \ge\ 7k+1+7$ ?

    $\displaystyle 4^k+(3)4^k\ \ge\ 7k+1+7$ ?

    If $\displaystyle 4^k\ \ge\ 7k+1$

    then $\displaystyle (3)4^k$ is definately greater than 7.

    Finally show P(k) it is valid for k=2
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by ADARSH View Post

    Assumption : P(k) is correct

    ie; $\displaystyle 2^k - k^2 >0 $

    Hence$\displaystyle 2^k> k^2 $

    Proof for P(k+1) using assumption:

    $\displaystyle 2^{k+1}- (k+1)^2 = 2 \times 2^k - k^2 -1-2k $


    since $\displaystyle 2^k > k^2 $
    Hence

    $\displaystyle 2 \times 2^k - k^2 -1-2k > 2 \times k^2 - k^2 -1-2k$

    $\displaystyle 2 \times 2^k - k^2 -1-2k > k^2 -1-2k$

    $\displaystyle 2 \times 2^k - k^2 -1-2k > (k+1)^2 $
    When we prove by Principle of Mathematical Induction, as much as it is possible, we want it be more convincing. Since the theorem says

    $\displaystyle P(k) \Rightarrow P(k+1)$

    It is more convincing to begin with $\displaystyle P(k)$ and end with $\displaystyle P(k+1)$. By beginning with P(k+1) is less desirable though it is not always the case for Strong Principle of Mathematical Induction.

    As much as we could, we would begin with

    $\displaystyle \begin{aligned}
    2^k-k^2 &>0\\
    2^k&>k^2 \text{. Now multiplying bothsides by 2, we obtain}\\
    2^{k+1}&>2k^2=K^2+k^2\geq K^2+ 5k=k^2+2k+3k\geq k^2+2k+15>k^2+k+1\\
    2^{k+1}&>k^2+k+1=(k+1)^2\\
    2^{k+1}&>(k+1)^2\\
    \end{aligned}$.

    Now subtract both sides by $\displaystyle (k+1)^2$, and we arrive at

    $\displaystyle 2^{k+1}-(k+1)^2>0$, which is precisely as desired; namely, P(k+1).

    $\displaystyle 2^{k+1}-(k+1)^2>0$.

    Notice that the first line of proof was $\displaystyle 2^k-k^2$
    and the last line of proof is $\displaystyle 2^{k+1}-(k+1)^2>0$.

    That is to say we have proved

    $\displaystyle P(k) \Rightarrow P(k+1)$ for $\displaystyle \forall k >4, k\in \mathbb{N}$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Mathematical Induction - Inequalities
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 14th 2011, 07:44 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. Mathematical Induction to Prove Inequalities
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Nov 28th 2009, 07:09 PM
  4. mathematical induction - inequalities
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Jun 16th 2008, 08:27 AM
  5. mathematical induction inequalities
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 27th 2007, 06:20 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum