Results 1 to 11 of 11
Like Tree3Thanks
  • 1 Post By topsquark
  • 1 Post By HallsofIvy
  • 1 Post By topsquark

Math Help - Im having trouble with mathematical induction

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    America
    Posts
    4

    Post Im having trouble with mathematical induction

    Please help solve this question for me.

    (a)Use mathematical induction to show that
    S(n) = 3 2 n-1 -2
    is the solution for the recurrence relation:
    T(n) = 2T(n 1) + 2 for n > 1 and T(1) = 1


    (b) If 1 is added to the recurrence relation such that:
    T(n) = 2T(n 1) + 3 for n > 1 and T(1) = 0
    What is the new equation for S(n)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by carlosgalhos View Post
    S(n) = 3 2 n-1 -2
    What is this line? I can't make heads nor tails out of it.

    -Dan

    Edit: Ah I see now. S_n = 3 \left ( 2^{n-1} \right ) - 2. Please use parenthesis.
    Last edited by topsquark; April 10th 2013 at 12:52 PM.
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2013
    From
    America
    Posts
    4

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by topsquark View Post
    What is this line? I can't make heads nor tails out of it.

    -Dan
    That doesnt matter
    I just need to prove that n>1 statement is true

    Just need to solve this equation and prove that its true: T(n) = 2T(n 1) + 2 for n > 1 and T(1) = 1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,449
    Thanks
    1864

    Re: Im having trouble with mathematical induction

    No, that's NOT what you were asked to do. You were asked to show that a certain function, which we cannot read because you are not using parentheses properly, is a solution to that equation. That is NOT the same as "solving the equation".
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by carlosgalhos View Post
    Please help solve this question for me.

    (a)Use mathematical induction to show that
    S(n) = 3 2 n-1 -2
    is the solution for the recurrence relation:
    T(n) = 2T(n 1) + 2 for n > 1 and T(1) = 1
    You can easily prove the base case, so I'll skip it.

    Assume that we know S_k = 3 \left ( 2^{k-1} \right ) - 2 for some k.

    We need to show that S_{k + 1} = 3 \left ( 2^k \right ) - 2 solves T_{k + 1} = 2 T_k + 2

    So plugging things in we need to show that
    3 \left ( 2^k \right ) - 2 = 2 \left [ 3 \left ( 2^{k-1} \right ) - 2 \right ] + 2

    Can you take it from here?

    -Dan
    Thanks from wilson208
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2013
    From
    America
    Posts
    4

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by topsquark View Post
    You can easily prove the base case, so I'll skip it.

    Assume that we know S_k = 3 \left ( 2^{k-1} \right ) - 2 for some k.

    We need to show that S_{k + 1} = 3 \left ( 2^k \right ) - 2 solves T_{k + 1} = 2 T_k + 2

    So plugging things in we need to show that
    3 \left ( 2^k \right ) - 2 = 2 \left [ 3 \left ( 2^{k-1} \right ) - 2 \right ] + 2

    Can you take it from here?

    -Dan
    Can you finished please as i dont really understand this question at all.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by carlosgalhos View Post
    Can you finished please as i dont really understand this question at all.
    You are in Discrete Math and you don't know how to do mathematical induction???

    You first prove the base case: Here you need to show that S_1 = 1 just as T_1 = 1. So we know that there exists some k such that S_k is the solution for T_k.

    Now you have to show that S_{k + 1} solves T_{k + 1}. I have set it up for you all you need to do is simplify the equation below.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2013
    From
    America
    Posts
    4

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by topsquark View Post
    You are in Discrete Math and you don't know how to do mathematical induction???

    You first prove the base case: Here you need to show that S_1 = 1 just as T_1 = 1. So we know that there exists some k such that S_k is the solution for T_k.

    Now you have to show that S_{k + 1} solves T_{k + 1}. I have set it up for you all you need to do is simplify the equation below.

    -Dan
    1.) 2 + 2^2 + 2^3 + 2^4 + ... + 2^n = 2^n+1 -2

    Let n=1

    2^n+1 -2 = 2^1+1 - 2 = 2^2 -2 = 4 - 2 = 2

    assume n=k
    2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 -2
    Let n=k+1
    2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 -2
    = [2 + 2^2 + 2^3 + 2^4 + ... + 2^k] + 2^k+1
    = [2^k+1 -2] + 2^k+1
    = 2 x 2^k+1 - 2
    = 2^1 x 2^k+1 - 2
    = 2^k+1+1 - 2
    = 2^(k+1)+1 - 2


    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Apr 2013
    From
    Ballynahinch
    Posts
    2

    Re: Im having trouble with mathematical induction

    I have come across the exact same question as part of my assignment. For part b:
    (b) If 1 is added to the recurrence relation such that:
    T(n) = 2T(n 1) + 3 for n > 1 and T(1) = 0
    What is the new equation for S(n)?
    My solution should be: S(n)=3(2^n-1) - 1

    Is this correct? Then I can just prove using the same induction method as above?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by carlosgalhos View Post
    1.) 2 + 2^2 + 2^3 + 2^4 + ... + 2^n = 2^n+1 -2

    Let n=1

    2^n+1 -2 = 2^1+1 - 2 = 2^2 -2 = 4 - 2 = 2

    assume n=k
    2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 -2
    Let n=k+1
    2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 -2
    = [2 + 2^2 + 2^3 + 2^4 + ... + 2^k] + 2^k+1
    = [2^k+1 -2] + 2^k+1
    = 2 x 2^k+1 - 2
    = 2^1 x 2^k+1 - 2
    = 2^k+1+1 - 2
    = 2^(k+1)+1 - 2


    Is this correct?
    You didn't prove anything that has to do with your problem.

    Okay. Step by step. First we need to establish a "base case." S is supposed to be a solution to the T equation, so we start there. The problem says that T_1 = 1. So does S_1 = 1?

    Now you can assume that the S solution for the T equation is valid for some specific value of k. Thus we know that S_k solves the T_k equation. In particular we suppose that
    S_k = 3(2^{k - 1}) - 2 is the solution of the equation T_k = 2T_{k - 1} + 2.

    Now we need to show that S_{k + 1} = 3(2^k) - 2 is the solution for T_{k + 1} = 2T_k + 2

    Can you finish from there?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Im having trouble with mathematical induction

    Quote Originally Posted by wilson208 View Post
    I have come across the exact same question as part of my assignment. For part b:


    My solution should be: S(n)=3(2^n-1) - 1

    Is this correct? Then I can just prove using the same induction method as above?
    For this one I think you have to solve the recurrence. There's no method that I know of that will get you the answer based on part a. (But I could be wrong.)

    Anyway I got S_n = 3(2)^{n - 1} - 3 by solving the recurrence directly.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical induction
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: August 26th 2011, 06:28 PM
  2. Mathematical induction?
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: June 10th 2011, 08:46 PM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Mathematical induction
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: March 9th 2010, 12:51 PM
  5. Mathematical induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: May 5th 2009, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum