Closed formula for finite product series I need to solve the recurrence:
$$
\begin{align*}
  T(n) &= kT\left(\frac{n}{2}\right) + (k - 2)n^3 \\
       &\textit{where}\; k \in \mathbb{Z}: k \geq 2 \\
       &= k(kT\left(\frac{n}{4} + \frac{(k - 2)n^3}{2}\right) + (k - 2)n^3 \\
       &= k^2T\left(\frac{n}{4}\right) + \frac{(k + 2)(k - 2)n^3}{2} \\
       &= k^2\left(kT\left(\frac{n}{8}\right) + \frac{(k + 2)(k - 2)n^3}{8}\right) + \frac{(k + 2)(k - 2)n^3}{2} \\
       &= k^3T\left(\frac{n}{8}\right) + \frac{(k^2 + 4)(k + 2)(k - 2)n^3}{8} \\
       &\dots \\
       &= k^iT\left(\frac{n}{2^i}\right) + \frac{(k - 2)n^3}{2^i}\prod_{j=1}^i(k^j+2^j)
\end{align*}
$$
But I don't know how can I develop this further. I know that the recursion will end at $i = \lg n$, but I don't know what to do with the product term.
 A: Here is a quick way to bound many kinds of functions defined by a recurrence if one is interested in the function's behaviour for large $n$.
Let $\lg x=\log_2 x$.
Suppose we are given a recurrence of the form $f(n)=cf(n/2)+p(n), f(1)=1$, where $p(n)$ is a function depending on $n$ and $c$ is a constant.
If $p(n)\ge 0$ for all $n\ge 1$, then
$f(n)\ge cf(n/2)$,
so $f(n)\ge c^{\lg n}= n^{\lg c}$.
Further, if $p(n)\ge p(n/2)$ for every $n\ge 2$, then
$f(n)\le c^{\lg n} + p(n)(c^{\lg n}-1)/(c-1)\le n^{\lg c}(1+p(n)/(c-1))$.
So $f(n)=\Omega(n^{\lg c})$ and $f(n)=O(n^{\lg c}p(n))$,
and it is easy to see that these expressions also hold for other constant values of $f(1)>0$.
The specific recurrence has $p(n)=(k-2)n^3$ and $c=k\ge 2$, which satisfy the conditions assumed for the inequalities to hold.
In particular, $f(n)=O(n^{3+\lg k})$ and $f(n)=\Omega(n^{\lg k})$ which is a polynomial in $n$ for fixed $k$.
(As stated the sequence of equations in the question has errors, and the final expression is $\Omega(n^{\lg n})$ which is not polynomial in $n$.)
