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
 30032013 00:01
Last edited by mos182; 30032013 at 00:39. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 2
 30032013 00: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
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 3
 30032013 00: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; 30032013 at 00:47. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 4
 30032013 01: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
 2 followers
 11 badges
 Send a private message to SubAtomic
Offline11ReputationRep: Follow
 5
 30032013 01: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 01:31. 
ghostwalker
 Follow
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 6
 30032013 09: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 15: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 15:22. 
ghostwalker
 Follow
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 8
 02042013 15: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 15: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 15: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
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 11
 02042013 15: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 16: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
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 13
 02042013 16: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 21:34. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 14
 02042013 19: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
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 15
 02042013 21: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 21:33. 
mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 16
 03042013 12: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
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 17
 03042013 14: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 18: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
 83 followers
 13 badges
 Send a private message to ghostwalker
 Study Helper
Offline13Study Helper Follow
 19
 03042013 19:12

mos182
 Follow
 2 followers
 1 badge
 Send a private message to mos182
 Thread Starter
Offline1ReputationRep: Follow
 20
 03042013 20:05
Reply
Submit reply
Related discussions:
 Advanced Higher Mathematics 2015/16  Discussion and Help ...
 To: Computer Science Grads
 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
 The Financier
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Moltenmo
Updated: April 3, 2013
Share this discussion:
Tweet