In a syllabus of mine, they try to find a closed form of the following recurrence relation
$\begin{align*} T(2k) &\leq 3T(k) + ck & k \geq 1\\ T(1) &= 1 \end{align*}$
The method I usually use to find the closed form of a recurrence is expand it a few times and try to find a pattern. Then I verify that pattern using induction.
In my syllabus they only show the verification part, by using $T(2^l) \leq c(3^l - 2^l)$ as hypothesis, where $c$ is chosen such $T(2)\leq c$ and $l \geq 1$.
So, I tried expanding the recurrence relation to see where I could find that pattern, but I don't get anything close to it.
For example:
$\begin{align*}T(2^l) &\leq 3(3T(2^{l-2})+c2^{l-2})+c2^{l-1}\\ &= 3^2T(2^{l-2})+3c2^{l-2}+c2^{l-1}\\ &= 3^2T(2^{l-2})+5c2^{l-2}\\ &\leq 3^2(3T(2^{l-3})+c2^{l-3})+5c2^{l-2}\\ &= 3^3T(2^{l-3})+3^2c2^{l-3}+10c2^{l-3} \end{align*}$
So, my guess is, since they multiply $3^l$ by $c$, you can subtract $c2^l$ and still remain bigger than $T(2^l)$. But, while expanding, I doubt I would have come up with that.
So my question: is there perhaps a method that I can use to find this hypothesis by expanding, and without to many `magic' manipulations to get to that hypothesis?