#### Archived

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

# Prove recursive formula using mathematical induction?

Recursive formula

##### Share on other sites

I'm guessing you have to prove the general solution to be $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 $T_n = 2^n -1$. Since the next case n+1 can be expressed using the recurrence relation as $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 $2^{n+1} - 1$, which is the required result.

1 person likes this

##### Share on other sites

Love mathematical induction.

The beauty of the concept.

2 people like this

##### 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