Is there an asymptotic for following recurrences?

Question

The recurrence I am interested is

$$T(2^k)=2T(2^{k-1})+aT(2^{k-2})+c_1\cdot 2^k$$ at an $a\in\mathbb R_{>0}$ and at a $c_1>0$.

Is there a closed form or a sharp asymptotic?

Answer 1

Set

$$S(k) \triangleq \frac{T(2^k)}{2^k}$$

Then after dividing everything in sight by $2^k$, your recurrence becomes

$$S(k) = S(k-1) + a S(k-2) + b$$

Here $a$ and $b$ are still arbitrary positive constants, but they are not the same constants we started with. This is a minor piece of bookkeeping at the end, though, which I will leave to you.

Now we have a linear recurrence, which is easily solved. According to wolframalpha:

$$S(k) = \frac{a c_1 (1 - \sqrt{4a+1})^k + a c_2 (1+\sqrt{4a+1})^k - b 2^k}{2^ka}$$ though you can use generating functions, linear algebra, etc. if you prefer. Here $c_1$ and $c_2$ are arbitrary parameters (related to the two base cases of the recursion).

Then unsubstituting gives

$$T(2^k) = \frac{a c_1 (1 - \sqrt{4a+1})^k + a c_2 (1+\sqrt{4a+1})^k - b 2^k}{a}$$

Of course, it is easy to get the asymptotics from this, if that's what you're interested in.

---

I hope this helps ^_^

Answer 2

Set $A_k = T(2^k, 2^k)$ and explore solutions of the form $A_k = a + 2^kb$.