Results 1 to 3 of 3

Math Help - Finite induction???

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    2

    Finite induction???

    I have a example problem that I can't figure out.

    We have listed in adjacent collumns the values of 4n and n^2 - 7 for the positive integers n, where 1 <= n <= 8

    n |4n| n^2-7
    1 | 4 | -6
    2 | 8 | -3
    3 | 12 | 2
    4 | 16 | 9
    5 | 20 | 18
    6 | 24 | 29
    7 | 28 | 42
    8 | 32 | 57

    From the table, we see that (n^2 - 7) < 4n for n = 1,2,3,4,5 but when n=6,7,8, we have 4n < (n^2-7). These last three observations lead us to conjecture: For all n>=6 4n < (n^2 - 7)

    Let S(n) denote the open statement 4n < (n^2 - 7). Then table confirms that s(6) is true and we have our basis step.
    In this example, the induction hypothesis is S(k): 4k < (k^2 - 7) where K is positive integer and K >= 6. In order to establish the inductive step, we need to obtain the truth of S(k + 1) frin that if s(k). That is, from 4k < (k^2-7) we must conclude that 4(k+1) < [(k+1)^2 - 7].
    Here are the necessary steps

    4k < (k^2 - 7) => 4k + 4 < (k^2 - 7) + 4 < (K^2 - 7) + (2k + 1)

    (because for K >= 6, we find 2k+1 >= 13 > 4), and

    4k + 4 < (K^2 - 7) + (2k+1) => 4(k+1) < (K^2 +2k + 1) - 7 = (k+1)^2-7


    My question is where in the world do the numbers I bolded come from????
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Induction

    Hello bwhit132
    Quote Originally Posted by bwhit132 View Post
    4k < (k^2 - 7) => 4k + 4 < (k^2 - 7) + 4 < (K^2 - 7) + (2k + 1)

    (because for K >= 6, we find 2k+1 >= 13 > 4), and

    4k + 4 < (K^2 - 7) + (2k+1) => 4(k+1) < (K^2 +2k + 1) - 7 = (k+1)^2-7


    My question is where in the world do the numbers I bolded come from????
    Welcome to Math Help Forum!

    There are two answers to your question. The first answer is to do with how it works; the second is to do with why. The rule explaining the how is:

    • We mayadd the same number to both sides of an inequality, and it remains true. In other words:


    • a<b \Rightarrow a\color{red}+c\color{black}<b\color{red}+c


    What's happened, then, is that 4 has been added to both sides of the inequality:

    4k<k^2-7\Rightarrow 4k\color{red}+4 \color{black} < (k^2-7) \color{red}+4

    That was how the + 4 appeared.

    But you may have asked: why should we want to add 4 to both sides of the inequality? The answer is that we need to create a term in 4(k+1) so that we can establish the truth of S(k+1).

    So that's why the + 4 appeared.


    The same thing happens again in the next stage, although it's not so clear this time. Let me put things the other way round, and you'll see how it works.

    k\ge 6\Rightarrow 2k+1 \ge 13 \Rightarrow 2k+1 > 4

    So, writing this the other way around, we get:

    4 < 2k+1 whenever k\ge 6

    If we now add (k^2-7) to both sides of 4 < 2k+1, we get:

    (k^2-7) +4 <(k^2-7) +2k+1

    So that's the how. Now for the why. Why look at 2k+1 at all? Well, it's to do with completing the square, because, again, we need to create a term in (k+1)^2 to establish the truth of S(k+1).

    And to make k^2 into (k+1)^2 we need to involve 2k+1, because (k+1)^2 = k^2+2k+1.

    Is that OK now?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    2
    Thank You so much. I am having a really hard time with discrete math and at least I understand this problem now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction proof concerning a finite sum inequality
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 11th 2011, 08:44 AM
  2. Distinct Bases for Finite Vector Spaces over Finite Fields
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: May 29th 2011, 12:31 PM
  3. Replies: 1
    Last Post: May 21st 2011, 04:17 AM
  4. Replies: 1
    Last Post: December 13th 2010, 02:21 AM
  5. Replies: 1
    Last Post: October 15th 2008, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum