Results 1 to 3 of 3

Math Help - mathematical induction proof

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    1

    mathematical induction proof

    f(n) = 2, for n=0.
    f(n) = 2f(n-1)-n+1, for n>=1.

    prove f(n)=(2^n)+n+1

    for n=0 -> f(n)=2.
    for n=k -> f(n)=(2^k)-k+1.
    for n=k+1 -> f(n)=(2^k+1)+k+2.

    Thats where i'm stuck. What am I supposed to do next?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Hi

    Your notation does not seem to be really appropriate
    I suggest
    u_0=2
    u_{n+1}=2 \:u_n - n

    You need to prove that u_n = 2^n+n+1

    2^0+0+1 = 2 = u_0 therefore it is true for n=0

    Suppose that it is true for n=k. This means that u_k = 2^k+k+1. You need to prove that u_{k+1} = 2^{k+1}+k+2

    You know that u_{k+1} = 2 \:u_k - k and that u_k = 2^k+k+1
    Substitute u_k = 2^k+k+1 in the expression of u_{k+1} to prove that u_{k+1} = 2^{k+1}+k+2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by blank View Post
    f(n) = 2, for n=0.
    f(n) = 2f(n-1)-n+1, for n>=1.

    prove f(n)=(2^n)+n+1

    for n=0 -> f(n)=2.
    for n=k -> f(n)=(2^k)-k+1.
    for n=k+1 -> f(n)=(2^k+1)+k+2.

    Thats where i'm stuck. What am I supposed to do next?
    f(0)=2
    f(n)=2f(n-1)-n+1,\ for\ n\ge1

    If you write a few terms, it appears f(n)=2^n+n+1

    Prove using induction that this is so.

    f(n)=2^n+n+1

    If this is true, then the following will also be true...

    f(n+1)=2^{n+1}+(n+1)+1=(2)2^n+(n+1)+1=2^n+2^n+(n+1  )+1

    =[2^n+n+1]+2^n+1=f(n)+2^n+1

    Therefore, if we can prove that f(n+1) really equals f(n)+2^n+1

    then we only need to prove it works for the first term, since a mathematical chain reaction has been set up..

    We attempt to prove it from f(n)=2f(n-1)-n+1.

    f(n+1)=2f(n)-(n+1)+1=2f(n)-n.

    The question is....

    Is 2f(n)-n=f(n)+2^n+1 ?

    Is 2f(n)-f(n)=2^n+n+1 ?

    f(n)=2^n+n+1

    true

    f(0)=1+0+1=2
    f(1)=2+1+1=4=2(2)-1+1 true
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2010, 05:36 PM
  2. Proof using mathematical induction
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: March 22nd 2010, 01:36 AM
  3. Mathematical induction proof, help?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 23rd 2010, 07:39 PM
  4. Proof by mathematical Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 20th 2009, 07:33 AM
  5. Proof by Mathematical induction!
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 30th 2008, 09:45 AM

Search Tags


/mathhelpforum @mathhelpforum