Proving the Solution to a Recurrence Relation Using Mathematical Induction

[jokiemay]

Hi all, I've been struggling with a large piece of coursework. been quite stressed latley and now I am 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


Ive answered so far
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

 

[mfb]

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.

12=1

This is wrong.

So n > 1 is True

Do you mean n=1?

= 2(2T(n − 2) + 1) + 1
=2( n + 4) 2n-1 -2

What happens here?

 

[Mark44]

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

I am confused by your notation.
Taken literally, 3 × 2 n-1 -2 = 6n-1-2=6n-3

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

 

[SammyS]

Hi all, I've been struggling with a large piece of coursework. been quite stressed latley and now I am 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

Ive answered so far
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

I'm really confused - can you guys help out

How is S_n related to T_n ?

As Mark44 pointed out, it appears that the formula for S_n should be

S_n = 3∙2^(n-1)-2​

Using the recurrence relation for T_n the first few values in the sequence [T_n] are

1, 4, 10, 22, 46, …​

 

[jokiemay]

sorry its T2=1 / 2 = 1

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

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

 

[HallsofIvy]

sorry its T2=1 / 2 = 1

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.

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

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

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?

 

[Mark44]

sorry its T2=1 / 2 = 1

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 let's me know that I have made a mistake.

 

[jokiemay]

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

 

[SammyS]

How is S_n related to T_n ?

As Mark44 pointed out, it appears that the formula for S_n should be

S_n = 3∙2^(n-1)-2   This has a typo.​

Using the recurrence relation for T_n the first few values in the sequence [T_n] are

1, 4, 10, 22, 46, …​

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

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

It appears that your problem should read something like:

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.)

 

[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

 

[mfb]

That is correct.

 

[SammyS]

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

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

Way to go !

 

[jokiemay]

Thanks all.

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

 

[SammyS]

Thanks all.

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

Write down the first several terms of this new sequence.