Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    1
    ReputationRep:
    Hello,

    Would really appreciate it if someone could help me with this question. I've tried it so many times and it just never seems to work out and I'm convinced that our lecturer hasn't write the question out properly because I can't work out a solution to it, seems like nobody in the class can work it out either.


    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

    (10 marks)
    • Thread Starter
    Offline

    1
    ReputationRep:
    Here's one (of many) of my workings out for this question:

    Step 1 ( n= 1)
    T(1) = 1
    S(1) = 3 x 2^1-1 -2 = 3 x 1 - 2 = 1

    Step 2 (n = k+1)

    Assume T(K) = S(K)

    T(k+1) = 2T(K) + 2
    = 2S(K) + 2

    = 2(3 x 2^k-1 -2) +2
    = 2(3 x 2^k-1) -4 + 2
    = 2(3 x 2^k-1) -2
    = 3x2^k-1 - 1

    ----------------------

    I'm pretty sure this isn't the correct solution because I think it has to equal S(N) which is = 3 x 2^n-1 -2



    Any guidance as to where I've went wrong and how to find the correct answer would be greatly appreciated
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by mos182)
    = 2(3 x 2^k-1 -2) +2
    = 2(3 x 2^k-1) -4 + 2
    = 2(3 x 2^k-1) -2
    = 3x2^k-1 - 1
    Unless I missed something, you just made a slip at the end.

    From 2(3 x 2^k-1) -2

    =3\times 2^k -2

= 3\times  2^{[(k+1)-1]}-2

=S(k+1)

    Edit: Last post for today.
    • Thread Starter
    Offline

    1
    ReputationRep:
    (Original post by ghostwalker)
    Unless I missed something, you just made a slip at the end.

    From 2(3 x 2^k-1) -2

    =3\times 2^k -2

= 3\times  2^{[(k+1)-1]}-2

=S(k+1)

    Edit: Last post for today.
    Thanks for helping me out, really appreciate it, however I don't understand how you came about that solution. Could you explain each step as to how you went from 2(3 x 2^k-1) -2 to the final solution?

    The 2 outside the bracket just seemed to cancel out, however it didn't divide the -2 which I originally had. Why did this happen?

    I also noticed how the power changed from 2^k-1 to 2^k. Is this because you're supposed to +1 to the power in the next step?

    I also noticed you got 2^(k+1)-1 from 2^k which I'm a bit confused about.
    Offline

    11
    ReputationRep:
    (Original post by mos182)
    I don't understand how you came about that solution. Could you explain each step as to how you went from 2(3 x 2^k-1) -2 to the final solution?
    I will try as ghostwalker has left the building.

    (Original post by mos182)
    The 2 outside the bracket just seemed to cancel out, however it didn't divide the -2 which I originally had. Why did this happen?
    What do you mean by this?

    (Original post by mos182)
    I also noticed how the power changed from 2^k-1 to 2^k. Is this because you're supposed to +1 to the power in the next step?
    This is just taking the 2 inside the brackets

    (Original post by mos182)
    I also noticed you got 2^(k+1)-1 from 2^k which I'm a bit confused about.
    They are equivalent. It is just power manipulation, as you know what you want to end up with.

    \displaystyle 2 \times 2 \times 2^k \equiv 2^2 \times 2^k \equiv 2^{k+2}
    • Study Helper
    Offline

    13
    Study Helper
    =3\times 2^k -2

= 3\times  2^{[(k+1)-1]}-2

=S(k+1)
    (Original post by mos182)
    The 2 outside the bracket just seemed to cancel out, however it didn't divide the -2 which I originally had. Why did this happen?

    I also noticed how the power changed from 2^k-1 to 2^k. Is this because you're supposed to +1 to the power in the next step?
    As I suspect you observed, the two didn't cancel, rather I combined the 2 with the 2^(k-1) to give 2^k

    I also noticed you got 2^(k+1)-1 from 2^k which I'm a bit confused about.
    You missed a set of brackets. It's 2^[(k+1)-1] from 2^k.
    What I'm doing here is getting the expression in the same form as S(k+1).

    And clearly k+1-1 = k, so the expressions have the same value.
    • Thread Starter
    Offline

    1
    ReputationRep:
    Once again, thanks for the response guys. Was working on Saturday and Monday and have also been taking a break from this work, so apologies for the late reply.

    I understand how you went from 2^k-1 to 2^k. 2 (3 x 2^k-1) - 2 , multiply the 2 ^k-1 by 2 and it gains a power, so then it goes to 2^k

    I'm guessing that you went from 3 x 2^k -2 to 3 x 2^[(k+1)-1) -2 because

    S(N) = 3 x 2^n-1 -2

    (n = k+1)

    3 x 2^[(k+1)-1] -2

    Is that correct?
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by mos182)

    I'm guessing that you went from 3 x 2^k -2 to 3 x 2^[(k+1)-1) -2 because

    S(N) = 3 x 2^n-1 -2

    (n = k+1)

    3 x 2^[(k+1)-1] -2

    Is that correct?
    Yes. Our final formula has to be identical in format to the definition of S(N) excepting it's evaluated at "k+1". This confirms that we have it correctly.
    Offline

    17
    ReputationRep:
    (Original post by mos182)
    Once again, thanks for the response guys. Was working on Saturday and Monday and have also been taking a break from this work, so apologies for the late reply.

    I understand how you went from 2^k-1 to 2^k. 2 (3 x 2^k-1) - 2 , multiply the 2 ^k-1 by 2 and it gains a power, so then it goes to 2^k

    I'm guessing that you went from 3 x 2^k -2 to 3 x 2^[(k+1)-1) -2 because

    S(N) = 3 x 2^n-1 -2

    (n = k+1)

    3 x 2^[(k+1)-1] -2

    Is that correct?
    Yes, it's because when you trying to show it's true for the k+1 case, you want to get it to *look* like the formula you're trying to prove, so you just manipulate it algebraically to show you have in fact shown it corresponds to the k+1 case of the equation.
    Offline

    17
    ReputationRep:
    (Original post by ghostwalker)
    Yes. Our final formula has to be identical in format to the definition of S(N) excepting it's evaluated at "k+1". This confirms that we have it correctly.
    Damn, I was too slow.
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by Noble.)
    Damn, I was too slow.
    Only by a few seconds. :smug:
    • Thread Starter
    Offline

    1
    ReputationRep:
    Okay so for my final answer I just show S(k+1) is equal to T(k+1) which was = 3 x 2^[(k+1)-1] -2

    I'm glad I've finally got this completed. When I first posted this thread, I was scared that my workings out would have been completely wrong, at least I got it right until it came towards the end of it.

    Have a second part, part b to complete now, so I'll hopefully be able to complete it now that I have a better understanding of this topic.

    Thanks again
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by mos182)
    Okay so for my final answer I just show S(k+1) is equal to T(k+1) which was = 3 x 2^[(k+1)-1] -2
    You have in fact shown that T(k+1) = S(k+1), and hence S(n) is a solution....

    I'm glad I've finally got this completed. When I first posted this thread, I was scared that my workings out would have been completely wrong, at least I got it right until it came towards the end of it.
    Yep, it was just the tidying up really.

    Have a second part, part b to complete now, so I'll hopefully be able to complete it now that I have a better understanding of this topic.

    Thanks again
    :cool:
    • Thread Starter
    Offline

    1
    ReputationRep:
    Tried to do B but it's not right.

    (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)?
    Prove it by induction.

    (10 marks)

    -------------------------------------------------------------------

    Below is my workings out:

    T(N) = 2T(n-1) +3

2T(n-1) = 2(2T(n-2) + 3 = 2^2T(n-2) + 2\times3

2^2T(n-2) = 2^2(2T(n-3) +3) = 2^3T(n-3) + 2^2\times3



2^{(n-1)}T(1) = 2^{(n-1)}(2T(0) +3) = 2^nT(0) + 2^{(n-1)} \times 3

2^{(n-1)}T(0) = 2^{(n-1)}(2T(0) +3) = 2^nT(0) + 2^{(n-1)} \times 3

*

*

Summing and cancelling gives

*

*

T(N) = 3 + 2\times3 + 2^2 \times 3 ... + 2^{(n-1)}\times3 + 2^n\times 3

= 3( 1 + 2 + 2^2 ... + 2^{(n-1)} + 2^n)

= 3( 2^0 + 2^1 + 2^2 .... + 2^n)

= 3(2^{(n+1)} )- / (2-1)

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

    I'm pretty sure this is wrong because when I put n = 1 I didn't get the same answer for T(1) and S(1):

    

T(1) = 0

S(1) = 3(2^{(n+1)} -1)

       = 3(2^{(1+1)} -1)

       = 3(2^2 -1)

       = 3(4-1) = 3 /times 3 = 9

    I'm guessing the answer is: 3(2^{(n-1)} -1)

    I'm not sure how to prove this and show this in my working out.

    It's really frustrating doing these questions because I've only been given 1 example for each scenario and the text book we were advised to buy doesn't have examples of this type of induction. The example I do have isn't that well explained, so it is at times hard to follow what exactly is happening at each stage. Hopefully some of my working out is correct.
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by mos182)
    Tried to do B but it's not right.

    (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)?
    Prove it by induction.

    (10 marks)

    -------------------------------------------------------------------

    Below is my workings out:

    T(N) = 2T(n-1) +3

2T(n-1) = 2(2T(n-2) + 3 = 2^2T(n-2) + 2\times3

2^2T(n-2) = 2^2(2T(n-3) +3) = 2^3T(n-3) + 2^2\times3



2^{(n-1)}T(1) = 2^{(n-1)}(2T(0) +3) = 2^nT(0) + 2^{(n-1)} \times 3

2^{(n-1)}T(0) = 2^{(n-1)}(2T(0) +3) = 2^nT(0) + 2^{(n-1)} \times 3

*

*

Summing and cancelling gives

*

*

T(N) = 3 + 2\times3 + 2^2 \times 3 ... + 2^{(n-1)}\times3 + 2^n\times 3

= 3( 1 + 2 + 2^2 ... + 2^{(n-1)} + 2^n)

= 3( 2^0 + 2^1 + 2^2 .... + 2^n)

= 3(2^{(n+1)} )- / (2-1)

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

    I'm pretty sure this is wrong because when I put n = 1 I didn't get the same answer for T(1) and S(1):
    When I sum I get:

    T(n)=2^nT(0)+3(1+2+2^2+...+2^{n-1})



=2^nT(0)+3(2^n-1)


    And since T(0) =0, we have

    T(n)=3(2^n-1)

    which seems to work at least for T(0) and T(1)

    PS: Please quote me if you want a reply - I didn't realise you'd posted again.
    • Thread Starter
    Offline

    1
    ReputationRep:
    Again a couple things I'm a little bit confused by and it'd help if you could explain them.

    (Original post by ghostwalker)
    When I sum I get:

    T(n)=2^nT(0)+3(1+2+2^2+...+2^{n-1})



=2^nT(0)+3(2^n-1)

    Why did you get (... +2^{n-1} )

    I'm guessing you just added up all the things multiplied by 3 yeah? Just noticed I didn't have 2^n multiplying by 3 in my workings out.

    (Original post by ghostwalker)

    (...+2^{n-1})



(2^n-1)
    How did you go from 2^{n-1} to 2^n-1?

    (Original post by ghostwalker)
    



=2^nT(0)+3(2^n-1)


    And since T(0) =0, we have

    T(n)=3(2^n-1)

    which seems to work at least for T(0) and T(1)
    So basically because T(0)= 0, then 2^n T(0) is also = 0, so you only have to concentrate with the 3(2^n -1) part for the final solution?
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by mos182)
    Why did you get (... +2^{n-1} )

    I'm guessing you just added up all the things multiplied by 3 yeah? Just noticed I didn't have 2^n multiplying by 3 in my workings out.
    Yep.

    How did you go from 2^{n-1} to 2^n-1?
    Sum of a geometric progression: \displaystyle S_n=\frac{a(1-r^n)}{1-r} where a(=1) is the first term, r(=2) the ratio, and n the number of terms.

    So basically because T(0)= 0, then 2^n T(0) is also = 0, so you only have to concentrate with the 3(2^n -1) part for the final solution?
    Yep.
    • Thread Starter
    Offline

    1
    ReputationRep:
    (Original post by ghostwalker)



    Sum of a geometric progression: \displaystyle S_n=\frac{a(1-r^n)}{1-r} where a(=1) is the first term, r(=2) the ratio, and n the number of terms.
    I'm unsure what you mean

    \displaystyle S_n=\frac{1(1-2^n)}{1-2}

    \displaystyle S_n=\frac{1(1-2^n)}{-1}

    What do you do after this? :confused:
    • Study Helper
    Offline

    13
    Study Helper
    (Original post by mos182)
    I'm unsure what you mean

    \displaystyle S_n=\frac{1(1-2^n)}{1-2}

    \displaystyle S_n=\frac{1(1-2^n)}{-1}

    What do you do after this? :confused:
    It simplifies to 2^n-1
    • Thread Starter
    Offline

    1
    ReputationRep:
    (Original post by ghostwalker)
    It simplifies to 2^n-1
    How? Sorry for all the questions, just want to understand how you came about your answers
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Would you like to hibernate through the winter months?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.