Forgot your password?
Or sign in with one of these services
This topic is now archived and is closed to further replies.
bobsmegdorf, September 23, 2013
Posted September 23, 2013
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 Tn 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.
Start by examining the relation
Find a new way to write down the general term
T(2) = 2*T(1) + 1T(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
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
Posted September 29, 2013