Results 1 to 14 of 14

Math Help - Proof by induction

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    145

    Proof by induction

    Hi,

    \rm{1.\ Prove\ by\ induction\ that\ 3^n \geq 1 + 2^n\ for\ all\ positive\ integers\ n.}
    A hint or two may suffice with this one.


    \rm{2.\ Show\ that\ all\ arithmetic\ progressions\ are\ divergent.}

    For any arithmetic progression, \displaystyle S_n =  \frac{n}{2}(2a + (n - 1)d), which always approaches infinity as n  \rightarrow \infty.
    Therefore any AP is divergent.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    1.

    Show P(1) is true

    P(1): \ 3\geq 3

    Assume P(k) is true and let n\leq k where k is a fixed arbitrary integer.

    P(k): \ 3^k\geq 1+2^k

    Show P(k+1) is true

    Hint: multiple P(k) by 3 and and remember positive terms can be dropped from the inequality.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    145
    Quote Originally Posted by dwsmith
    P(1): \ 3\geq 3

    Assume P(k) is true and let n\leq k where k is a fixed arbitrary integer.
    P(k): \ 3^k\geq 1+2^k

    Show P(k+1) is true
    3^{k + 1} \geq 3 + 3 \cdot 2^k
    3^{k + 1} \geq 3 \cdot 2^k

    Is that it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Hellbent View Post
    3^{k + 1} \geq 3 + 3 \cdot 2^k
    3^{k + 1} \geq 3 \cdot 2^k

    Is that it?
    3\cdot 3^k\geq 3(1+2^k)\Rightarrow 3^{k+1}\geq 3+(2+1)2^k\Rightarrow 3^{k+1}\geq 1+2+2^{k+1}+2^k

    k>0

    What can we do to the inequality since k is positive now?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2009
    Posts
    145
    \Rightarrow 3^{k+1}\geq 1+2+2^{k+1}+2^k
    How did you arrive at that?

    Quote Originally Posted by dwsmith View Post
    What can we do to the inequality since k is positive now?
    I do not know.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Hellbent View Post
    How did you arrive at that?


    I do not know.
    3\cdot 3^k\geq 3\cdot(1+2^k)\Rightarrow 3^{k+1}\geq 3+3\cdot 2^k\Rightarrow 3^{k+1}\geq (2+1)+(2+1)2^k
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Hellbent View Post
    I do not know.
    You can drop positive values from the inequality.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    3^{k+1}\geq 1+2+2^{k+1}+2^k\Rightarrow 3^{k+1}\geq 1+2^{k+1}+(2+2^k)

    (2+2^k)>0

    You can drop them from the inequality.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466
    Quote Originally Posted by Hellbent View Post
    Hi,

    \rm{1.\ Prove\ by\ induction\ that\ 3^n \geq 1 + 2^n\ for\ all\ positive\ integers\ n.}
    A hint or two may suffice with this one.


    \rm{2.\ Show\ that\ all\ arithmetic\ progressions\ are\ divergent.}
    For any arithmetic progression, \displaystyle S_n =  \frac{n}{2}(2a + (n - 1)d), which always approaches infinity as n  \rightarrow \infty.
    Therefore any AP is divergent.
    The problem asked you to show that any arithmetic progression is divergent. You have shown that the series formed by that progression is divergent, not the progression itself.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Hellbent View Post
    Hi,

    \rm{1.\ Prove\ by\ induction\ that\ 3^n \geq 1 + 2^n\ for\ all\ positive\ integers\ n.}
    A hint or two may suffice with this one.

    P(k)

    3^k\ \ge\ 1+2^k\;\;?


    P(k+1)

    3^{k+1}\ \ge\ 1+2^{k+1}\;\;?

    Try to show that P(k+1) will definately be true "if" P(k) is true.

    Therefore, write P(k+1) in terms of P(k) in order to draw a comparison.


    Proof

    "If" P(k) is true, then

    3^k\ \ge\ 1+2^k

    \Rightarrow\ 3\left(3^k\right)\ \ge\ 3\left(1+2^k\right)

    \Rightarrow\ 3^{k+1}\ \ge\ 3+(3)2^k

    \Rightarrow\ 3^{k+1}\ \ge\ 1+2+(2)2^k+2^k

    \Rightarrow\ 3^{k+1}\ \ge\ 1+2^{k+1}+\left(2+2^k\right)

    Hence, if P(k) is true, then P(k+1) is true, since 2+2^k>0

    Now all you need do is prove P(k) is true for the first relevant value of "n".
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Sep 2009
    Posts
    145
    Quote Originally Posted by HallsofIvy
    The problem asked you to show that any arithmetic progression is divergent. You have shown that the series formed by that progression is divergent, not the progression itself.
    S_{n} = \frac{1}{2}(2a + (n - 1)d)
    with finite values for a and d, as n increases, so does the value of S_n.
    if n \rightarrow \infty, then S_n \rightarrow \infty in a positive or negative sense depending on the series.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    You are showing that the "sum" of the terms, which is the "series", does not converge (your formula is missing an "n").

    You are asked to show that the "sequence", the list of terms of T_n or U_n, doesn't converge.

    U_n=a+(n-1)d
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Sep 2009
    Posts
    145
    Quote Originally Posted by Archie Meade View Post
    You are showing that the "sum" of the terms, which is the "series", does not converge (your formula is missing an "n").

    You are asked to show that the "sequence", the list of terms of T_n or U_n, doesn't converge.

    U_n=a+(n-1)d
    U_{n} = a + (n - 1)d
    with finite values for a and d, as n increases, so does the value of U_n.
    if n \rightarrow \infty, then U_n \rightarrow \infty in a positive or negative sense depending on the series.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Yes,

    to be mathematically concise, you could write

    U_n=a+nd-d=(a-d)+nd=n\left(\frac{a-d}{n}+d\right)

    n\rightarrow\infty\Rightarrow\ U_n\rightarrow\ nd

    \Rightarrow\ U_n\rightarrow\pm\infty
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 10:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 17th 2010, 07:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 04:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum