Results 1 to 6 of 6

Math Help - Four mathematical induction problems

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    11

    Four mathematical induction problems

    Hi...
    I have an exam soon, and didn't succeed to prove those...



    Thank you so much!!!
    Last edited by mr fantastic; November 1st 2010 at 01:40 AM. Reason: Title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by rectangle View Post
    Hi...
    I have an exam soon, and didn't succeed to prove these...

    Thank you so much!!!
    For 1.

    P(k)

    \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt  {k}

    P(k+1)

    \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k+1}}>\sq  rt{k+1}

    Show that "if" P(k) is valid, then P(k+1) "must therefore" also be valid.
    Hence, write P(k+1) in terms of P(k).

    Proof

    If P(k) is valid, then

    \displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{  1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}

    If \displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}>\sqrt{k+1}, then P(k+1) will be valid.

    \displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}=\frac{\sqrt{k+1}\sqr  t{k}+1}{\sqrt{k+1}}

    If \displaystyle\frac{\sqrt{k+1}\sqrt{k}+1}{\sqrt{k+1  }}>\sqrt{k+1}

    then

    \displaystyle\sqrt{k+1}\sqrt{k}+1>k+1

    It can be seen that this is true since \sqrt{k+1}>\sqrt{k}

    hence, you need to examine the case for n=2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    11
    Quote Originally Posted by Archie Meade View Post
    For 1.

    P(k)

    \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt  {k}

    P(k+1)

    \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k+1}}>\sq  rt{k+1}

    Show that "if" P(k) is valid, then P(k+1) "must therefore" also be valid.
    Hence, write P(k+1) in terms of P(k).

    Proof

    If P(k) is valid, then

    \displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{  1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}

    If \displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}>\sqrt{k+1}, then P(k+1) will be valid.

    \displaystyle\ \sqrt{k}+\frac{1}{\sqrt{k+1}}=\frac{\sqrt{k+1}\sqr  t{k}+1}{\sqrt{k+1}}

    If \displaystyle\frac{\sqrt{k+1}\sqrt{k}+1}{\sqrt{k+1  }}>\sqrt{k+1}

    then

    \displaystyle\sqrt{k+1}\sqrt{k}+1>k+1

    It can be seen that this is true since \sqrt{k+1}>\sqrt{k}

    hence, you need to examine the case for n=2.
    Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    For 2.

    \displaystyle\sqrt{a+\sqrt{a+\sqrt{a+....}}}\le\ \frac{1+\sqrt{4a+1}}{2}

    You want to show that this inequality holds true for any level of nesting.
    Suppose the above inequality is at a nesting depth of n or k

    P(k)

    \displaystyle\sqrt{a+\sqrt{a+\sqrt{a+....}}}\le\ \frac{1+\sqrt{4a+1}}{2}

    for a nesting depth of k.

    Add a to both sides and take the square root to get a depth of k+1.

    a+\displaystyle\sqrt{a+\sqrt{a+\sqrt{a+....}}}\le\ a+\frac{1+\sqrt{4a+1}}{2}

    \displaystyle\sqrt{a+\sqrt{a+\sqrt{a+\sqrt{a+....}  }}}\le\ \sqrt{a+\frac{1+\sqrt{4a+1}}{2}}

    The above has a nesting depth of k+1.

    P(k) will definately be valid if \displaystyle\sqrt{\frac{2a+1+\sqrt{4a+1}}{2}}\le\ \frac{1+\sqrt{4a+1}}{2}

    If this is so, then P(k) is always true.

    Squaring both sides...

    \displaystyle\frac{2a+1+\sqrt{4a+1}}{2}\le\frac{1+  2\sqrt{4a+1}+4a+1}{4} ??

    It's now a simple matter to verify this.

    Finally, test for n=1 or k=1..

    \displaystyle\sqrt{a}\le\ \frac{1+\sqrt{4a+1}}{2} ?

    2\sqrt{a}\le\ 1+\sqrt{4a+1} ?

    \sqrt{4a}\le\ 1+\sqrt{4a+1}

    which is certainly true as \sqrt{4a+1}>\sqrt{4a}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    No.3 is straightforward.


    For x_k>0, prove by induction that

    \left(x_1+x_2+.....+x_n\right)\left(\frac{1}{x_1}+  \frac{1}{x_2}+....+\frac{1}{x_n}\right)\ \ge\ n


    P(k)

    \left(x_1+x_2+.....+x_k\right)\left(\frac{1}{x_1}+  \frac{1}{x_2}+....+\frac{1}{x_k}\right)\ \ge\ k


    P(k+1)

    \left(x_1+x_2+.....+x_k+x_{k+1}\right)\left(\frac{  1}{x_1}+\frac{1}{x_2}+....+\frac{1}{x_k}+\frac{1}{  x_{k+1}}\right)\ \ge\ k+1


    Try to show that if P(k) is true, then it causes P(k+1) to also be true.

    Proof

    \left(x_1+.....+x_k+x_{k+1}\right)\left(\frac{1}{x  _1}+....+\frac{1}{x_k}+\frac{1}{x_{k+1}}\right)=

    \left(x_1+.....+x_k\right)\left(\frac{1}{x_1}+....  +\frac{1}{x_k}+\frac{1}{x_{k+1}}\right)+x_{k+1}\le  ft(\frac{1}{x_1}+....+\frac{1}{x_k}+\frac{1}{x_{k+  1}}\right)=

    \left(x_1+.....+x_k\right)\left(\frac{1}{x_1}+....  +\frac{1}{x_k}\right)+\left(x_1+....+x_k}\right)\l  eft(\frac{1}{x_{k+1}}\right)+x_{k+1}\left(\frac{1}  {x_1}+....+\frac{1}{x_{k+1}}\right)=

    \left(x_1+.....+x_k\right)\left(\frac{1}{x_1}+....  +\frac{1}{x_k}\right)+\frac{x_{k+1}}{x_{k+1}}+\lef  t(x_1+....+x_k}\right)\left(\frac{1}{x_{k+1}}\righ  t)+x_{k+1}\left(\frac{1}{x_1}+....+\frac{1}{x_k}\r  ight)

    Whether or not P(k) being valid causes P(k+1) to be valid should now be clear.

    Finally test for n=1.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    No.4 was a bit more challenging.

    Writing it in the way we normally use "k",

    P(k)

    \displaystyle\sqrt{\sum_{i=1}^k\left(x_i-y_i\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^k\left(x_i\right)^2}+\sqrt{\sum_{  i=1}^k\left(y_i\right)^2}

    P(k+1)

    \displaystyle\sqrt{\sum_{i=1}^{k+1}\left(x_i-y_i\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^{k+1}\left(x_i\right)^2}+\sqrt{\s  um_{i=1}^{k+1}\left(y_i\right)^2}

    We want to show that if P(k) is valid, then it will cause P(k+1) to be valid also.
    Hence we try to write P(k+1) so that it contains the P(k) expression.
    Then we can draw the conclusion.

    Proof

    \displaystyle\sqrt{\sum_{i=1}^{k+1}\left(x_i-y_i\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^{k+1}\left(x_i\right)^2}+\sqrt{\s  um_{i=1}^{k+1}\left(y_i\right)^2}\;\;?

    Rewriting P(k+1)..

    \displaystyle\sqrt{\sum_{i=1}^k\left(x_i-y_i\right)^2+\left(x_{k+1}-y_{k+1}\right)^2}\;\; \le\ \sqrt{\sum_{i=1}^k\left(x_i\right)^2+\left(x_{k+1}  \right)^2}+\sqrt{\sum_{i=1}^k\left(y_i\right)^2+\l  eft(y_{k+1}\right)^2}\;\;?

    Squaring both sides,

    \displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2+\left(x_{k+1}-y_{k+1}\right)^2\;\;\le

    \displaystyle\sum_{i=1}^k\left(x_i\right)^2+\left(  x_{k+1}\right)^2+\sum_{i=1}^k\left(y_i\right)^2+\l  eft(y_{k+1}\right)^2+2\sqrt{\sum_{i=1}^k\left(x_i\  right)^2+\left(x_{k+1}\right)^2}\sqrt{\sum_{i=1}^k  \left(y_i\right)^2+\left(y_{k+1}\right)^2}\;?


    Subtracting \left(x_{k+1}-y_{k+1}\right)^2=\left(x_{k+1}\right)^2+\left(y_{k  +1}\right)^2-2\left(x_{k+1}\right)\left(y_{k+1}\right) from both sides,

    \displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2\;\;\le\ \sum_{i=1}^k\left(x_i\right)^2+\sum_{i=1}^k\left(y  _i\right)^2+\left(x_{k+1}\right)^2-\left(x_{k+1}\right)^2+\left(y_{k+1}\right)^2-\left(y_{k+1}\right)^2+

    \displaystyle\ +2\left(x_{k+1}\right)\left(y_{k+1}\right)+2\sqrt{  \sum_{i=1}^k\left(x_i\right)^2+\left(x_{k+1}\right  )^2}\sqrt{\sum_{i=1}^k\left(y_i\right)^2+\left(y_{  k+1}\right)^2}\;\;?

    Hence, our rewritten P(k+1) is

    \displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2\;\;\le\ \sum_{i=1}^k\left(x_i\right)^2+\sum_{i=1}^k\left(y  _i\right)^2+2\left(x_{k+1}\right)\left(y_{k+1}\rig  ht)+

    \displaystyle\ +2\sqrt{\sum_{i=1}^k\left(x_i\right)^2+\left(x_{k+  1}\right)^2}\sqrt{\sum_{i=1}^k\left(y_i\right)^2+\  left(y_{k+1}\right)^2}\;\;?


    Rewriting P(k) by squaring both sides, to examine P(k+1)...

    \displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2\;\;\le\ \sum_{i=1}^k\left(x_i\right)^2+\sum_{i=1}^k\left(y  _i\right)^2+2\sqrt{\sum_{i=1}^k\left(x_i\right)^2}  \sqrt{\sum_{i=1}^k\left(y_i\right)^2}

    Examining the above rewritten P(k+1) and P(k) propositions,
    it's easy to see that the RHS of the P(k+1) expression is greater than the RHS of the P(k) expression,
    while the LHS is the same for both.

    Therefore, if P(k) is valid, P(k+1) will as a result, also be valid.

    Hence you only need to test for n=1 or k=1.
    Last edited by Archie Meade; November 4th 2010 at 06:53 AM. Reason: 2 typos
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 7th 2010, 08:05 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 6th 2009, 10:08 PM
  5. Mathematical induction problems
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 8th 2007, 08:53 AM

Search Tags


/mathhelpforum @mathhelpforum