Results 1 to 4 of 4

Math Help - Proving recursive function via mathematical induction (EASY, but need a boost)

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    USA
    Posts
    6

    Proving recursive function via mathematical induction (EASY, but need a boost)

    This was a sample problem discussed in class that I already have the solution to, but I am having trouble understanding the highlighted section. Please be very detailed with your explanation. Thank you in advance!

    Let f be defined recursively by:
    Initial condition: f(0)=1
    Recursive step: f(n)=2f(n-1)+1

    For the function f above, prove that for all n, f(n)=2n+1-1.

    ----------------------------------------------------------------
    SOLUTION:

    Proof by induction:
    1) Basis step:
    Prove that f(0)=2n+1-1
    f(0)=20+1-1 is true
    because 1=1
    2) Inductive step:
    Inductive hypothesis: Assume that for some n>=0, f(n)=2n+1-1.
    We need to use this hypothesis to prove that f(n+1)=2n+2-1.
    Proof: Assume that the inductive hypothesis is true,
    (I DO NOT UNDERSTAND HOW THE RIGHT SIDE OF THE BELOW EQUATION (2f(n)+1) WAS FOUND)
    then f(n+1)=2f(n)+1 (via Recursive definition of f)
    =2(2n+1-1)+1 (via Inductive hypothesis)
    =2n+2-2+1
    =2n+1-1

    # END OF PROOF
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Proving recursive function via mathematical induction (EASY, but need a boost)

    After having shown the base case is true, I would state the induction hypothesis P_n:

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

    Using the recursive definition, we may state:

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

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

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

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

    We have derived P_{n+1} from P_n, thereby completing the proof by induction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member ModusPonens's Avatar
    Joined
    Aug 2010
    Posts
    125
    Thanks
    14

    Re: Proving recursive function via mathematical induction (EASY, but need a boost)

    You compose the functions on each side of the equation of the recursive step with g(k)=k+1 and obtain the second equation in red with k instead of n.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2012
    From
    USA
    Posts
    6

    Re: Proving recursive function via mathematical induction (EASY, but need a boost)

    Sorry for the late reply. Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: April 11th 2011, 11:26 AM
  2. Mathematical induction, proving inequation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2010, 05:21 AM
  3. easy? proving a linear function
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 1st 2010, 03:17 AM
  4. Need help proving mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 29th 2009, 08:16 AM
  5. Need help proving!! Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 06:38 PM

Search Tags


/mathhelpforum @mathhelpforum