Page 2 of 2 FirstFirst 12
Results 16 to 19 of 19
Like Tree1Thanks

Math Help - Proving inequality through induction

  1. #16
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    I can that this is showing 2^{N+1}\geq 4(N+1). But I can't see how this equality is equal to 2^{N} or 4N + 4N > 4N + 4 = 4(N+1)
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    I understand now the equality sign only applies to the expression on the side of the inequality sign on which it is placed, rather than equating the whole inequality expression.

    Given the explanation posted in the thread I'm still confused about why the working I have posted gives the inequality to larger than 4k - 4 rather than 4(K+1).

    Is this something to do with the shifting of the inequality sign?

    Why have they chosen to express the ineqaulity sign as they have?
    Last edited by alyosha2; May 21st 2012 at 09:54 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    After many hours of intense thought I came to a solution and thought I should post it so as to not to leave the thread without clousre in case someone has a similar problem. Also I hope it will help crystallise the idea for me and perhaps I've even got it wrong so others could refine it.

    First a word about precedence and equality signs. It's usual to think of the equality sign as having the lowest possible precedence.This however is not the case when considering inequality signs which appear to have an even lower precedence than equality signs. So a = b > c = d is (a = b) > (c = d) or just b > c and not a = (b > c) = d.

    So, to my original problem


    (fixed some errors)

    2^k - 4k

    2^k > 4k = 2^k - 4k > 0

    2^{k+1} - 4(k+1) = 2 * 2^{k} - 4(k+1)

    > 2 * 4k - 4(k+1) using





    Now the idea here was to show by induction that this inequality would hold for large enough values of n. It was noted that If the inequality held this would mean that .

    This means that if 4k is less than 2^k then subtracting the smaller from the larger would leave a difference that is larger than 0.

    Now to show that the equality will hold we will have to show that if the difference left by 2^k - 4k < 0 then the difference left by 2^{k+1} - 4(k+1) > 0.

    How can we do this?

    Well we use 2^{k+1} - 4(k+1) to express the difference of the proposition with k+1 and note that this can be expressed in terms of k as 2 * 2^{k} - 4(k+1).

    Now if we assume that we can use this inequality to find an expression that the difference of the proposition with (K+1) will be larger than and if this expression is larger than 0 we know the proposition will hold.

    We do this by manipulating the left side of the inequality 2^k to become 2 * 2^{k} - 4(k+1) and then do the same to the other the other side of the inequality to maintain equality with original.

    So 2 * 2^k - 4(k+1) < 2 * 4k - 4(k+1)

    The left hand side of this equality simplifes to 8k - 4k - 4 and then to 4k - 4 and this expression will equate to greater than 0 for k > 1. So we know that the proposition will hold for some value k > 1.



    This is my understanding and it seems satisfactory as far as I can tell. Please let me know if I have made any wrong assumptions or have completely misunderstood.



    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,367
    Thanks
    736

    Re: Proving inequality through induction

    you have some errors in your proof, but the idea is almost right.

    we want to prove that if n > 4, then 2n > 4n.

    we want to prove this for all natural numbers greater than 4. the "way" we do this is prove it for n = 5, and then show:

    true for n implies true for n+1.

    putting these two facts together gives us:

    true for 5 implies true for 6 implies true for 7 implies true for 8 implies....(and so on, forever).

    which is the same as saying "true for all n > 4".

    it is important we not neglect the "base case", here, it is n = 5:

    25 = 32, and this is indeed greater than 4*5 = 20.

    now, IF 2n > 4n for some natural number n (greater than 4), we'd like to prove the statement is also true for "the next number" n+1.

    that is, GIVEN that 2n > 4n, PROVE that 2n+1 > 4(n+1).

    now an equivalent way of stating this, is:

    given 2n - 4n > 0, prove 2n+1 - 4(n+1) > 0.

    so starting with the expression 2n+1 - 4(n+1), we observe that:

    2n+1 - 4(n+1) = 2(2n) - 4(n+1).

    and since 2n > 4n (our given assumption, or induction hypothesis)

    we know that 2(2n) > 2(4n), and 2(4n) = 8n. so

    2n+1 - 4(n+1) > 8n - 4(n+1).

    but 4(n+1) = 4n + 4, so 8n - 4(n+1) = 8n - 4n - 4 = 4n - 4.

    so so far we know that 2n+1 - 4(n+1) > 4n - 4.

    but we also know that n > 4, so that 4n > 16, so 4n - 4 > 16 - 4, and of course 16 - 4 = 12.

    using the transitivity of "greater than" ( that is if a > b and b > c, then a > c), and the fact that 12 > 0, we have from:

    n > 4, that 4n - 4 > 12 > 0, so 4n - 4 > 0 (for any n > 4. it's also true for "other smaller n", but smaller values aren't of interest to us, because we're only proving our "main result" for n > 4).

    then we have from 2n+1 - 4(k+1) > 4n - 4, and n - 4 > 0,

    that 2n+1 - 4(n+1) > 0, and therefore that:

    2n+1 > 4(n+1). and since that was what we set out to prove from our start of the assumption that 2n > 4n,

    we have "completed the induction", and shown the inequality holds for all natural numbers greater than 4.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Induction: an inequality
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: June 16th 2011, 06:42 PM
  2. Induction Inequality
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 17th 2011, 01:47 PM
  3. Replies: 3
    Last Post: December 12th 2010, 01:16 PM
  4. Induction for an inequality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 5th 2010, 10:51 PM
  5. induction inequality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2010, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum