Results 1 to 6 of 6

Thread: 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; Nov 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
    4
    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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt {k}$

    P(k+1)

    $\displaystyle \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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{ 1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$

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

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

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

    then

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

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

    hence, you need to examine the case for $\displaystyle 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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+....+\frac{1}{\sqrt{k}}>\sqrt {k}$

    P(k+1)

    $\displaystyle \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 \displaystyle\ 1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{k}}+\frac{ 1}{\sqrt{k+1}}>\sqrt{k}+\frac{1}{\sqrt{k+1}}$

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

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

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

    then

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

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

    hence, you need to examine the case for $\displaystyle 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
    4
    For 2.

    $\displaystyle \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 $\displaystyle n$ or $\displaystyle k$

    P(k)

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

    for a nesting depth of k.

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

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

    $\displaystyle \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 $\displaystyle k+1.$

    P(k) will definately be valid if $\displaystyle \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 \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 $\displaystyle n=1$ or $\displaystyle k=1..$

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

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

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

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

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


    For $\displaystyle x_k>0,$ prove by induction that

    $\displaystyle \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)

    $\displaystyle \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)

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

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

    $\displaystyle \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)=$

    $\displaystyle \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)=$

    $\displaystyle \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 $\displaystyle n=1.$
    Follow Math Help Forum on Facebook and Google+

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

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

    P(k)

    $\displaystyle \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 \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 \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 \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 \displaystyle\sum_{i=1}^k\left(x_i-y_i\right)^2+\left(x_{k+1}-y_{k+1}\right)^2\;\;\le$

    $\displaystyle \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 $\displaystyle \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 \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 \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 \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 \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 \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 $\displaystyle n=1$ or $\displaystyle k=1.$
    Last edited by Archie Meade; Nov 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: Oct 7th 2010, 08:05 PM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jul 8th 2009, 12:27 AM
  4. Mathematical Induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Mar 6th 2009, 10:08 PM
  5. Mathematical induction problems
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Nov 8th 2007, 08:53 AM

Search Tags


/mathhelpforum @mathhelpforum