Results 1 to 5 of 5

Thread: Mathematical Induction

  1. #1
    Junior Member Cthul's Avatar
    Joined
    Mar 2010
    Posts
    71

    Mathematical Induction


    My friend needs help and requires this work to be done by today. I hope it won't trouble anyone to elaborate how to do so.
    EDIT: Where it says $\displaystyle 2^{2}$, it's supposed to be $\displaystyle 2^{N}$ I apologies.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    The induction hypothesis is
    $\displaystyle k < 2^k$

    You assume that you have already proved this for k. Now you use this to prove $\displaystyle k+1 < 2^{k+1}$

    So $\displaystyle k+1 < 2^{k} + 1$ just adds 1 to both sides of the induction hypothesis.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Cthul's Avatar
    Joined
    Mar 2010
    Posts
    71
    Quote Originally Posted by friend
    then they change $\displaystyle 2^{k+1}$ into $\displaystyle 2^{k}+2^{k}$ because $\displaystyle 1<2^k$
    and set that to $\displaystyle 2\times2^k=2^{k+1}$
    He still doesn't get it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10
    $\displaystyle \displaystyle
    k<2^k \ \mbox{multiple by 2}\Rightarrow \ 2k<2*2^k\Rightarrow k+k<2^{k+1}$

    Since $\displaystyle \displaystyle k\geq n\geq 1$, we can take the 2nd k and set it equal to 1 without loss of generality.

    $\displaystyle \displaystyle k+1<2^{k+1}$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    Quote Originally Posted by Cthul View Post

    My friend needs help and requires this work to be done by today. I hope it won't trouble anyone to elaborate how to do so.
    EDIT: Where it says $\displaystyle 2^{2}$, it's supposed to be $\displaystyle 2^{N}$ I apologies.

    P(k)

    $\displaystyle k<2^k$


    P(k+1)

    Replace k with k+1

    $\displaystyle k+1<2^{k+1}\;\;\;?$


    Proof

    $\displaystyle k<2^k\Rightarrow\ 2(k)<2\left(2^k\right)$

    $\displaystyle 2k<2^{k+1}$

    $\displaystyle 2k=k+k\Rightarrow\ (k+k)<2^{k+1}$

    Since it is proven for the base case k=0 or k=1,

    then $\displaystyle (k+1)<(k+k)$ for $\displaystyle k>1$

    Therefore, if $\displaystyle k<2^k$

    then $\displaystyle (k+1)<2^{k+1}$ since $\displaystyle (k+1)<(k+k)$ for $\displaystyle k>1$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jul 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum