Results 1 to 8 of 8

Math Help - 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:

    P(5) = 2^5 - 5^2 = 32 - 25 = 7

    Now 7 >0 hence its correct for n = 5

    Assumption : P(k) is correct

    ie; 2^k - k^2 >0

    Hence  2^k> k^2

    Proof for P(k+1) using assumption:

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


    since 2^k > k^2
    Hence

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

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

    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; March 17th 2009 at 03: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; March 17th 2009 at 03: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
    1
    2^n-n^2\ >0

    is the same as

    2^n>n^2

    Here is another way to prove it by induction..

    P(k)

    2^k>k^2 for k>4

    P(k+1)

    Try to prove that

    2^k>k^2

    causes

    2^{k+1}>(k+1)^2

    Proof

    2^{k+1}>(k+1)^2 ?

    (2)2^k>k^2+2k+1 ?

    2^k+2^k>k^2+2k+1 ?

    If k>4, then 2^k>2k+1

    hence, if 2^k>k^2

    then

    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
    1
    For the 3rd..

    P(k)

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

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

    P(k+1)

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

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

    Proof

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

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

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

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

    then (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; 2^k - k^2 >0

    Hence  2^k> k^2

    Proof for P(k+1) using assumption:

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


    since 2^k > k^2
    Hence

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

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

    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

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

    It is more convincing to begin with P(k) and end with 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

    \begin{aligned}<br />
2^k-k^2 &>0\\<br />
2^k&>k^2 \text{. Now multiplying bothsides by 2, we obtain}\\<br />
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\\<br />
2^{k+1}&>k^2+k+1=(k+1)^2\\<br />
2^{k+1}&>(k+1)^2\\<br />
\end{aligned}.

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

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

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

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

    That is to say we have proved

    P(k) \Rightarrow P(k+1) for \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: March 14th 2011, 08:44 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. Mathematical Induction to Prove Inequalities
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 28th 2009, 08:09 PM
  4. mathematical induction - inequalities
    Posted in the Algebra Forum
    Replies: 1
    Last Post: June 16th 2008, 09:27 AM
  5. mathematical induction inequalities
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 27th 2007, 07:20 AM

Search Tags


/mathhelpforum @mathhelpforum