Prove recursive formula using mathematical induction?

[bobsmegdorf]

Recursive formula

Edited October 7, 2013 by bobsmegdorf

[ctrls]

I'm guessing you have to prove the general solution to be 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 . Since the next case n+1 can be expressed using the recurrence relation as , you just have to substitute T_n with the general solution you assumed. With a bit of rearranging you will end up at , which is the required result.

[-._._.-]

Love mathematical induction.

The beauty of the concept.

[rinik]

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

Edited September 25, 2013 by rinik

[bobsmegdorf]

thanks

Edited October 7, 2013 by bobsmegdorf