Results 1 to 3 of 3

Thread: 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:


    • $\displaystyle 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:

    $\displaystyle 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 $\displaystyle 4(k+1)$ so that we can establish the truth of $\displaystyle 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.

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

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

    $\displaystyle 4 < 2k+1$ whenever $\displaystyle k\ge 6$

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

    $\displaystyle (k^2-7) +4 <(k^2-7) +2k+1$

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

    And to make $\displaystyle k^2$ into $\displaystyle (k+1)^2$ we need to involve $\displaystyle 2k+1$, because $\displaystyle (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: Jun 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: Dec 13th 2010, 02:21 AM
  5. Replies: 1
    Last Post: Oct 15th 2008, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum