How would I go about converting this recurrence relation to closed form?

Question

So I looked at a part of code and came up with a recurrence relation for it and I got: $$T(0) = 1,$$ $$T(n) = 3 + 2T(n-1).$$

Then I solved it using substitution and got:

$$T(n) = 2^i*T(n-i)+3(2^i-1).$$

I'm confused on the steps to convert this to closed form, any guidance would be much appreciated!

Answer 1

You should have a base case, likely $T(0)$ or $T(1)$. You choose $i$ to make use of the one you get. You can take $i=n-1$ and write $T(n)=2^{n-1}T(1)+3\cdot (2^{n-1}-1)$ if you have a value for $T(1)$.