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)

mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 1
 29032013 23:01
Last edited by mos182; 29032013 at 23:39. 
Revision help in partnership with Birmingham City University

mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper 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. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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. 
SubAtomic
 Follow
 3 followers
 11 badges
 Send a private message to SubAtomic
Offline11ReputationRep: 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. 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper 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. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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. 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper 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. 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper Follow
 11
 02042013 14:39
(Original post by Noble.)
Damn, I was too slow. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper 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. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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. 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper 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. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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) 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper 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? 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: 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? 
ghostwalker
 Follow
 87 followers
 15 badges
 Send a private message to ghostwalker
 Study Helper
Offline15Study Helper Follow
 19
 03042013 18:12

mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 20
 03042013 19:05
 1
 2
Related discussions
 Advanced Higher Mathematics 2015/16  Discussion and Help ...
 To: Computer Science Grads
 Question about Mathematics and Computer Science?
 Edexcel A2 Mathematics: Further Pure FP2 6668 01  06 June ...
 Computer Science at University of Bath
 Maths modules most relevant to computer science:
 Edexcel Mathematics: Further Pure FP1 6667 01  19 May ...
 Studying Mathematics at Manchester
 Studying Mathematics at Manchester
 Oxford Computer Science (CS) Students and Applicants
Related university courses

Mathematics
University of Birmingham

Financial Mathematics
University of Hertfordshire

Mathematics and Physics
University of Dundee

Mathematics for Finance and Management
University of Portsmouth

Mathematics
University of Winchester

Mathematics
University of Oxford

Mathematics (Including Year Abroad)
University of Essex

Mathematics and Statistics (including placement year)
University of Essex

Mathematics with Foundation
Durham University

Pure Mathematics (Fast Track)
University of St Andrews
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.
 SherlockHolmes
 Notnek
 charco
 Mr M
 Changing Skies
 F1's Finest
 rayquaza17
 RDKGames
 davros
 Gingerbread101
 Kvothe the Arcane
 TeeEff
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 TheAnxiousSloth
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Labrador99
 EmilySarah00
 thekidwhogames
 entertainmyfaith
 Eimmanuel