Results 1 to 6 of 6

Math Help - Mathematical Induction

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    9

    Mathematical Induction

    plz find the attached file.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aamirpk4 View Post
    plz find the attached file.
    here's the first. i want you to try the third question on your own, and post your solution.

    this is how math. induction works.

    we begin with some statement that depends on a set of integers, usually the whole set of natural numbers. to prove the statement is true by math. induction, we do the following procedure.

    we prove that the statement is true for the first integer it is claimed to be true for, usually this is 1. so we find P(1) and show that the statement is true if we replace n with 1. if it's true, we are in good shape. this step is called the basis

    next we move on to the inductive step or inductive hypothesis. in this step, we assume that the statement is true for some integer k which is greater than or equal to the base integer. and then we prove that if it's true for this term, then it will be true for the next term, that is, the k + 1 term.

    so iduction in a nutshell:

    given a statement P(n) for n \geq 1

    - prove P(1) is true
    - assume P(k) is true for some k \geq 1, and derive that P(k + 1) is true

    so here is the first:

    Let P(n): " \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2n - 1)(2n + 1)} = \frac {n}{2n + 1} for all integers n \geq 1 "

    Then P(1): \frac {1}{(2(1) - 1)(2(1) + 1)} = \frac {1}{1 \cdot 3} = \frac {1}{2(1) + 1} = \frac {1}{3}, which is true.

    So P(1) is true

    Assume P(k) is true for some k \geq 1, we show that P(k + 1) is true.

    So we have:

    P(k): \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2k - 1)(2k + 1)} = \frac {k}{2k + 1}

    add the k + 1 term to both sides, we get:

    \frac {1}{1 \cdot 3} + ... + \frac {1}{(2k - 1)(2k + 1)} + \frac {1}{(2(k + 1) - 1)(2(k + 1) + 1)} = \frac {k}{2k + 1} + \frac {1}{(2(k + 1) - 1)(2(k + 1) + 1)}

    .................................................. .................................. = \frac {k}{2k + 1} + \frac {1}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {k(2k + 3) + 1}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {2k^2 + 3k + 1}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {(2k + 1)(k + 1)}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {k + 1}{2k + 3}

    .................................................. .................................. = \frac {k + 1}{2(k + 1) + 1}

    .................................................. .................................. = P(k + 1)

    Thus, P(k + 1) is true.

    Therefore P(n) is true for all n \geq 1 by the method of Mathemtaical Induction




    If there is any step that confuses you, say so
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aamirpk4 View Post
    plz find the attached file.
    Here's the second question:

    Prove \sqrt {3} + \sqrt {7} is irrational


    Proof: Assume to the contrary that \sqrt {3} + \sqrt {7} is rational

    Then \left( \sqrt {3} + \sqrt {7} \right)^2 = 10 + 2 \sqrt {21} is rational as well.

    But 10 + 2 \sqrt {21} is only rational if 2 \sqrt {21} is rational. So 2 \sqrt {21} is rational and so \sqrt {21} is rational.

    Assume \sqrt {21} is rational.

    Then \sqrt {21} = \frac {a}{b} for a,b \in \mathbb {Z} \mbox { , } b \neq 0, and we may further assume that \frac {a}{b} is in lowest terms

    This means that 21 = \frac {a^2}{b^2}

    Which means 21 b^2 = a^2

    But this means 21 divides a^2, which means 21 divides a (can you prove this?)

    Since 21 divides a, a = 21 m for m \in \mathbb {Z}

    So 21 b^2 = a^2 \Longleftrightarrow 21 b^2 = \left( 21 m \right)^2

    So 21 b^2 = 21^2 m^2

    So b^2 = 21 m^2

    But this means 21 divides b^2, so 21 divides b

    So we can write b = 21 n for some n \in \mathbb {Z}

    Therefore, \frac {a}{b} = \frac {21m}{21n} = \frac {m}{n}

    But this is a contradiction, since we assumed \frac {a}{b} is in lowest terms. So we have that \sqrt {21} is NOT rational, therefore \sqrt {3} + \sqrt {7} is NOT rational. Thus, \sqrt {3} + \sqrt {7} is irrational.

    QED.



    What I did with \sqrt {21} is the standard way I was taught to prove something is irrational. I admit it is a beautiful method that makes you wonder how the guy that came up with it did come up with it, but I never really liked it. Another way to prove something is irrational was found in one of my other texts, I kind of like such a proof better. It goes like this.

    Prove \sqrt {21} is irrational.

    Proof: Consider the equation x^2 - 21 = 0

    By the Rational Roots Theorem, the ONLY rational solutions to this equation are \pm 1 \mbox { , } \pm 3 \mbox { , and } \pm 7

    But \sqrt {21} is a solution to the above equation. Therefore, \sqrt {21} is not a rational number

    QED

    Of course, this is not a contradiction proof, but it's a good proof to know if you are not restricted to doing a particular kind of proof. As you can see, it's much shorter.


    Also, you may be tempted to begin with, "if \sqrt {3} + \sqrt {7} is rational, then \sqrt {3} is rational, and \sqrt {7} is rational." And then you would proceed to show that both are irrational, and come up with a contradiction. This would be wrong, as it is possible to add two irrational numbers and get a rational one (can you prove this?)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Jhevon View Post
    Prove \sqrt {3} + \sqrt {7} is irrational
    Nothing wrong with your proof. You taken the Pythagorean version and modifed it well. But here is another one.

    ----
    Here is another:

    \mbox{ Let }x=\sqrt{3}+\sqrt{7}
    Then,
    x^2 = 10 + 2\sqrt{21}
    x^2-10 = 2\sqrt{21}
    x^4 - 20x^2+100 = 84
    x^4 - 20x^2 + 16 = 0

    By rational root theorem none of \pm 1,\pm 2,\pm 4,\pm 8,\pm 16 solves this.
    So it has irrational real roots or complex.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,719
    Thanks
    634
    Hello, aamirpk4!

    Had to do some acrobatics for #3 . . .


    3) Prove by induction that: . 3^n < n! .for  n > 6.

    The base case is n = 7.
    . . Is 3^7 \,<\,7!\:?\quad\Rightarrow\quad 2187 \,<\,5040 . . . yes!


    Assume S(k) is true: . 3^k \,< \,k!

    Multiply both sides by 3: . 3\!\cdot\!3^k \:<\:3\!\cdot\!k!

    . . and we have: . 3^{k+1}\:<\:3\!\cdot\!k! . [1]


    And now a short detour . . .

    . . Since k > 6, we know that: . 3 \:<\:k+1

    . . Multiply both sides by k!\!:\;\;3\cdot k! \:<\:(k+1)\cdot k!

    . . Hence, we have: . 3\!\cdot\!k! \:< \: (k+1)!


    Combined with [1], we have: . 3^{k+1} \:<\: 3\!\cdot\!k! \:<\: (k+1)!


    We have proved S(k+1) . . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Math Engineering Student
    Krizalid's Avatar
    Joined
    Mar 2007
    From
    Santiago, Chile
    Posts
    3,654
    Thanks
    13
    Quote Originally Posted by Jhevon View Post
    here's the first. i want you to try the third question on your own, and post your solution.

    this is how math. induction works.

    we begin with some statement that depends on a set of integers, usually the whole set of natural numbers. to prove the statement is true by math. induction, we do the following procedure.

    we prove that the statement is true for the first integer it is claimed to be true for, usually this is 1. so we find P(1) and show that the statement is true if we replace n with 1. if it's true, we are in good shape. this step is called the basis

    next we move on to the inductive step or inductive hypothesis. in this step, we assume that the statement is true for some integer k which is greater than or equal to the base integer. and then we prove that if it's true for this term, then it will be true for the next term, that is, the k + 1 term.

    so iduction in a nutshell:

    given a statement P(n) for n \geq 1

    - prove P(1) is true
    - assume P(k) is true for some k \geq 1, and derive that P(k + 1) is true

    so here is the first:

    Let P(n): " \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2n - 1)(2n + 1)} = \frac {n}{2n + 1} for all integers n \geq 1 "

    Then P(1): \frac {1}{(2(1) - 1)(2(1) + 1)} = \frac {1}{1 \cdot 3} = \frac {1}{2(1) + 1} = \frac {1}{3}, which is true.

    So P(1) is true

    Assume P(k) is true for some k \geq 1, we show that P(k + 1) is true.

    So we have:

    P(k): \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2k - 1)(2k + 1)} = \frac {k}{2k + 1}

    add the k + 1 term to both sides, we get:

    \frac {1}{1 \cdot 3} + ... + \frac {1}{(2k - 1)(2k + 1)} + \frac {1}{(2(k + 1) - 1)(2(k + 1) + 1)} = \frac {k}{2k + 1} + \frac {1}{(2(k + 1) - 1)(2(k + 1) + 1)}

    .................................................. .................................. = \frac {k}{2k + 1} + \frac {1}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {k(2k + 3) + 1}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {2k^2 + 3k + 1}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {(2k + 1)(k + 1)}{(2k + 1)(2k + 3)}

    .................................................. .................................. = \frac {k + 1}{2k + 3}

    .................................................. .................................. = \frac {k + 1}{2(k + 1) + 1}

    .................................................. .................................. = P(k + 1)

    Thus, P(k + 1) is true.

    Therefore P(n) is true for all n \geq 1 by the method of Mathemtaical Induction




    If there is any step that confuses you, say so
    Hey Jhevon

    If you wanna align, use

    \begin{aligned}

    \end{aligned}

    Example:

    \begin{aligned}
    a&=b\\
    a^2&=ab\\
    a^2-b^2&=ab-b^2\\
    (a+b)(a-b)&=b(a-b)
    \end{aligned}

    This yields

    <br />
\begin{aligned}<br />
a&=b\\<br />
a^2&=ab\\<br />
a^2-b^2&=ab-b^2\\<br />
(a+b)(a-b)&=b(a-b)<br />
\end{aligned}

    This was, the LaTeX's contribution.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum