# Mathematical induction

1. Feb 14, 2013

### jokiemay

Hi all, ive been struggling with a large peice of coursework. been quite stressed latley and now im struggling while aproaching my deadline. i need help answering this question.

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

Base T(1)=1
LS : T2 = 12 = 1 RS: 1T = 1(1) = 1
So n > 1 is True
Induction T(n) = 2T(n-1) + 2 for all n > 1

T(n) = 2T(n – 1) + 3
= 2T (n -1) + 3
= 2(2T(n − 2) + 1) + 1
=2( n + 4) 2n-1 -2
= 6n -3
S(n) = 3 × 2 n-1 -2

Im really confused - can you guys help out

Last edited by a moderator: Feb 14, 2013
2. Feb 14, 2013

### Staff: Mentor

Re: Induction

I am confused by your notation.
Taken literally, 3 × 2 n-1 -2 = 6n-1-2=6n-3
But why did you write it so complicated? In addition, it does not satisfy the recurrence relation.
This is wrong.
Do you mean n=1?
What happens here?

3. Feb 14, 2013

### Staff: Mentor

Re: Induction

Might this be what the OP means?

S(n) = 3 * 2 n-1 -2

As just plain text, this would be written as S(n) = 3 * 2^(n-1) -2

4. Feb 14, 2013

### SammyS

Staff Emeritus
How is Sn related to Tn ?

As Mark44 pointed out, it appears that the formula for Sn should be
Sn = 3∙2(n-1)-2
Using the recurrence relation for Tn the first few values in the sequence [Tn] are
1, 4, 10, 22, 46, …​

5. Feb 15, 2013

### jokiemay

sorry its T2=1 / 2 = 1

the confusing part is why Sn is related to Tn , im just going to base it on Tn.
The statment n > 1 is true

and by the replys i seem to have gone very wrong somewhere?

6. Feb 15, 2013

### HallsofIvy

I Have no idea what this means! According to "T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1", T(2)= 2T(1)+ 2= 2(1)+ 2= 4.

You still haven't told us what "S(n) = 3 × 2 n-1 -2" means! Is it, as has been suggested, S(n)= 3(2^(n-1))- 2?

7. Feb 15, 2013

### Staff: Mentor

What you're saying is that 1/2 = 1. Even my dog knows this is not true. If I put only half the usual amount of food in his bowl, he lets me know that I have made a mistake.

8. Feb 16, 2013

### jokiemay

cheers for your help, @ mark, the layout that the coursework has been set is confusing me. im emailing my leacturer to enquire about the questiion.

9. Feb 16, 2013

### SammyS

Staff Emeritus
Well, I had a typo in Post #4. Quoted above.

Sn should be:   Sn = 3∙2(n-1) - 2 .

Use mathematical induction to show that the sequence defined by:
S(n) = 3∙2 n-1 - 2 ​
is the same sequence defined by recursion as:
T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1​

(If you calculate the first few terms, you will see that they definitely start out the same.)

10. Feb 16, 2013

### jokiemay

Base S(1)=1, so T(1)=S(1)
for some n, T(n)=S(n), then:
T(n+1) = 2T(n)+2 = 2(3×2^(n-1) -2) +2 = 3 × 2^n-4+2 = 3×2^n-2 = S(n+1)

Proof that T(n)=S(n) then T(n+1)=S(n+1), and as we have T(1)=S(1) i have proven by induction that T(n)=S(n) for any n in the positive integers

Last edited: Feb 16, 2013
11. Feb 16, 2013

### Staff: Mentor

That is correct.

12. Feb 16, 2013

### SammyS

Staff Emeritus
So, you went from deciding to "take a hit" on this problem, to solving it.

Way to go !

13. Feb 17, 2013

### jokiemay

Thanks all.

Ive to change T(1) = 1 to T(1)=0 and re write the equation.

14. Feb 18, 2013

### SammyS

Staff Emeritus
Write down the first several terms of this new sequence.

Prove $5^n+9<6^n$ for $n\epsilon N|n\ge2$ by induction Jun 9, 2017