Problem solving

For this problem solving blog entry I have chosen to look back on how I solved the first question to my term test #2.

---------------------------------------------------------------------------------------------

The question was: Use any techniques you like to guess a closed form for T(n). State your guess, and prove it correct.

VnEN T(n) = { 1, if n = 0
2T(n-1), if n > 0

------------------------------------------------------------------------------------------------

First thing was understanding the problem, I read the instructions and twaht the problem asked me to do and I looked at what I was given and tried to formulate some scrap work to try and make a proof. The important data was where the question stated the T(n) function, and this is mostly what you would work with. We know that n is a natural number so n >= 0, and we know T(n) when n is >= 0. This data is sufficient to solve the problem because the function is defined for all intervals of n.

When first looking at this quesiton I had noticed that I had seen this type of question before. There was a similar example in the lecture notes that Prof. Heap had wrote up for us on the projector. I remembered that the example had to do with finding the closed form of a function and unwinding. So next I started to write down some rough notes and began to unwind the function. After unwinding it 3 times I recognized a pattern and used this to derive or guess a closed form. With a closed form I could show how the function would look after n iterations and using this information i could prove that the closed form is correct.

Unwinding the problem I derive:
T(n) = 2T(n-1) (given)
= 2(2T(n-2)) = 4T(n-2) = 2^2T(n-2) (given, unwinding)
= 4(2T(n-3)) = 8T(n-3) = 2^3T(n-3) (given, unwinding)
= 2^nT(n-n) (derived closed form)
= 2^n

P(n): T(n) = 2^n, VnEN

Base Case: n = 0: 2^n = 2^0 = 1 = T(0)
So P(0) is true.

Induction Step: Assume nEN, and P(n) is true.
Then T(n+1) = 2T((n+1) - 1)
= 2T(n)
= 2(2n)
= 2^n+1
Therefore T(n) => T(n+1), VnEN.

You can chekc this result with the function you are given, and see that since using the give data I can find a value that corresponds with my closed form thus this answer must be correct. I don't see another way to go about solving this problem but it looks to me that using unwinding and finding a close form is a very simple way to solve this problem. Induction will probabaly be used to prove this problem regardless of how you guessed the closed form. The steps taken to prove this problem can be used to solve different problems that are similar. As noted above this problem was similar to an example given in class, so the foresight in solving this problem can be used to help solve other similar problems.