Archived

This topic is now archived and is closed to further replies.

bobsmegdorf

Prove recursive formula using mathematical induction?

I'm guessing you have to prove the general solution to be gif.latex?T_n=2^n - 1 and for all positive integers?

Proving it for n=1 is simple since it's given it's a base case, then you just assume gif.latex?T_n = 2^n -1. Since the next case n+1 can be expressed using the recurrence relation as gif.latex?T_{n+1}=2T_n + 1, you just have to substitute Tn with the general solution you assumed. With a bit of rearranging you will end up at gif.latex?2^{n+1} - 1, which is the required result.

1 person likes this

Share this post


Link to post
Share on other sites

Start by examining the relation

Find a new way to write down the general term

T(2) = 2*T(1) + 1
T(3) = 2*T(2) + 1
T(4) = 2*T(3) + 1

T(5) = 2*T(4) + 1

now substitute the previous term in to the next

T(3) = 2(2*T(1) + 1) +1 = 4*T(1) + 4 - 1 .............There is a reason I am writing 3 as 4 - 1 just follow the stuff below

T(4)= 8*T(1) + 8 -1

analyze the above and deduce that

T(n) = 2^(n-1)*T(1) + 2^(n-1) - 1

Prove by mathematical induction

show for n =some number

assume n=k

T(k) = 2^(k-1)*T(1) + 2^(k-1) - 1

Prove for T(k+1)

T(k+1) = 2 * (2^(k-1) T(1) + 2^(k-1) - 1) + 1

just simplify this and you will get what you are looking for then substituent it with 2 * T(k) + 1

I took some time and did some research and I think this will answer all the questions you have http://www.math.dartmouth.edu/archive/m19w03/public_html/Section4-2.pdf

You will also see that there are other ways to approach this.

You won't see problems like these in final IB exams. If you are not doing this for your EE or portfolio stop and practice for the final exams this will just distract you from the things you need to know. Coming from a person who loves mathematics and is trying to get accepted to a good uni at the moment

2 people like this

Share this post


Link to post
Share on other sites