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^n1 2
is the solution for the recurrence relation:
T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1
(10 marks)

 Follow
 1
 29032013 23:01
Last edited by mos182; 29032013 at 23:39. 
 Follow
 2
 29032013 23:07
Here's one (of many) of my workings out for this question:
Step 1 ( n= 1)
T(1) = 1
S(1) = 3 x 2^11 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^k1 2) +2
= 2(3 x 2^k1) 4 + 2
= 2(3 x 2^k1) 2
= 3x2^k1  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^n1 2
Any guidance as to where I've went wrong and how to find the correct answer would be greatly appreciated 
 Follow
 3
 29032013 23:45
(Original post by mos182)
= 2(3 x 2^k1 2) +2
= 2(3 x 2^k1) 4 + 2
= 2(3 x 2^k1) 2
= 3x2^k1  1
From 2(3 x 2^k1) 2
Edit: Last post for today.Last edited by ghostwalker; 29032013 at 23:47. 
 Follow
 4
 30032013 00:11
(Original post by ghostwalker)
Unless I missed something, you just made a slip at the end.
From 2(3 x 2^k1) 2
Edit: Last post for today.
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^k1 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. 
 Follow
 5
 30032013 00:30
(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^k1) 2 to the final solution?
(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?
(Original post by mos182)
I also noticed how the power changed from 2^k1 to 2^k. Is this because you're supposed to +1 to the power in the next step?
(Original post by mos182)
I also noticed you got 2^(k+1)1 from 2^k which I'm a bit confused about.
Last edited by SubAtomic; 30032013 at 00:31. 
 Follow
 6
 30032013 08:19
(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^k1 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.
What I'm doing here is getting the expression in the same form as S(k+1).
And clearly k+11 = k, so the expressions have the same value. 
 Follow
 7
 02042013 14:18
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^k1 to 2^k. 2 (3 x 2^k1)  2 , multiply the 2 ^k1 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^n1 2
(n = k+1)
3 x 2^[(k+1)1] 2
Is that correct?Last edited by mos182; 02042013 at 14:22. 
 Follow
 8
 02042013 14:33
(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^n1 2
(n = k+1)
3 x 2^[(k+1)1] 2
Is that correct? 
 Follow
 9
 02042013 14:34
(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^k1 to 2^k. 2 (3 x 2^k1)  2 , multiply the 2 ^k1 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^n1 2
(n = k+1)
3 x 2^[(k+1)1] 2
Is that correct? 
 Follow
 10
 02042013 14:35
(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. 
 Follow
 11
 02042013 14:39
(Original post by Noble.)
Damn, I was too slow. 
 Follow
 12
 02042013 15:05
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 
 Follow
 13
 02042013 15:16
(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
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 againLast edited by ghostwalker; 02042013 at 20:34. 
 Follow
 14
 02042013 18:20
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:
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):
I'm guessing the answer is:
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. 
 Follow
 15
 02042013 20:30
(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:
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):
And since T(0) =0, we have
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.Last edited by ghostwalker; 02042013 at 20:33. 
 Follow
 16
 03042013 11:46
Again a couple things I'm a little bit confused by and it'd help if you could explain them.
I'm guessing you just added up all the things multiplied by 3 yeah? Just noticed I didn't have multiplying by 3 in my workings out.
(Original post by ghostwalker)
And since T(0) =0, we have
which seems to work at least for T(0) and T(1) 
 Follow
 17
 03042013 13:30
(Original post by mos182)
Why did you get
I'm guessing you just added up all the things multiplied by 3 yeah? Just noticed I didn't have multiplying by 3 in my workings out.
How did you go from 2^{n1} to 2^n1?
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? 
 Follow
 18
 03042013 17:50
(Original post by ghostwalker)
Sum of a geometric progression: where a(=1) is the first term, r(=2) the ratio, and n the number of terms.
What do you do after this? 
 Follow
 19
 03042013 18:12

 Follow
 20
 03042013 19:05
Reply
Submit reply
Related discussions:
 To: Computer Science Grads
 Advanced Higher Mathematics 2015/16  Discussion and Help ...
 Question about Mathematics and Computer Science?
 Computer Science at University of Bath
 Edexcel Mathematics: Further Pure FP1 6667 01  19 May ...
 Studying Mathematics at Manchester
 Studying Mathematics at Manchester
 Oxford Computer Science (CS) Students and Applicants
 Self teach ALevel Maths 2015
 AQA A2 Mathematics MPC3 Core 3  Friday 5th June 2015 ...
TSR Support Team
We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.
This forum is supported by:
 SherlockHolmes
 Notnek
 charco
 Mr M
 TSR Moderator
 Nirgilis
 usycool1
 Changing Skies
 James A
 rayquaza17
 RDKGames
 randdom
 davros
 Gingerbread101
 Kvothe the Arcane
 Airmed
 The Financier
 The Empire Odyssey
 Protostar
 surina16
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
Updated: April 3, 2013
Share this discussion:
Tweet