You are Here: Home >< Maths

# HELP - Computer Mathematics Induction watch

1. 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)
2. 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
3. (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

Edit: Last post for today.
4. (Original post by ghostwalker)
Unless I missed something, you just made a slip at the end.

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

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.
5. (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.

6. (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.
7. 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?
8. (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.
9. (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.
10. (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.
11. (Original post by Noble.)
Damn, I was too slow.
Only by a few seconds.
12. 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
13. (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
14. 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 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.
15. (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):
When I sum I get:

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.
16. 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:

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.

(Original post by ghostwalker)

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

(Original post by ghostwalker)

And since T(0) =0, we have

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?
17. (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.
Yep.

How did you go from 2^{n-1} to 2^n-1?
Sum of a geometric progression: 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.
18. (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.
I'm unsure what you mean

What do you do after this?
19. (Original post by mos182)
I'm unsure what you mean

What do you do after this?
It simplifies to
20. (Original post by ghostwalker)
It simplifies to

### Related university courses

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:
Updated: April 3, 2013
Today on TSR

### Edexcel C3 Maths Unofficial Markscheme

Find out how you've done here

### 1,034

students online now

Exam discussions

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams