Consider the recursive function $f(n)=3f(n/4)+2n $, $f(16)=32.$
Where n is always a power of 4 greater than 16.
We must find a closed form utilizing substitutions.
So, after one substitution, f(n) could be written as:
$$ f(n)= 3^{2} \cdot f(\frac{n}{4^{2}})+\frac{3\cdot2n}{4}+2n $$ And after two substitutions, it would look like:
$$ f(n)= 3^{3} \cdot f(\frac{n}{4^{3}})+ \frac{3^{2}\cdot2n}{4^{2}}+\frac{3\cdot2n}{4}+2n $$
In a standardized form:
$$ f(n)= 3^{k} \cdot f(\frac{n}{4^{k}})+ \frac{3^{k-1}\cdot2n}{4^{k-1}}+ ... +\frac{3\cdot2n}{4}+2n $$
Consider that this series: $\frac{3^{k-1}\cdot2n}{4^{k-1}}+ ... +\frac{3\cdot2n}{4}+2n $ Is a geometric series that should evaluate to $8n$ right?
And also, since we need $f(\frac{n}{4^{k}})=f(16)$, then $k=\frac{\log(n)}{log(4)}-2$
Then f(n) should be:
$$f(n)=3^{\log{n}/log{4} -2}\cdot32 + 8n$$
Yet this is obviously wrong by simply plugging in values. I believe my mistake is that the geometric series does not converge to $8n$, since I am completely disregarding the variable $k$ and that seems wrong.
Any help on how to fix this would be appreciated.