Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$

Question

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$.

Is the attached picture the correct answer?

Answer 1

Using Brute force here is not that ugly. Define: $u(n)=\frac{f(n)}{4^n}$. Then we have to look at : $$ u(n)=u(n-1)+\frac{n}{4^n} $$ which is a very easy to solve: $$ u(n)=u(0)+\sum_{k=1}^n\frac{k}{4^k}< u_0+\frac 49=c $$ hence $f(n)<c4^n$. This is a tight upper bound because it is the supremum of $f(n)$.

Answer 2

Unfortunately ,master's method is not applicable here because the difference between f(n) and $n^{\log_ba}$ is not polynomial.Other than master's method ,you can solve it directly rather in a long but credible solution by putting $n=log_2m$, so that the expression becomes:- $$f(\log_{2} m)=4f(\log_2\frac{m}{2})-\log_2m\tag{..1}$$ i.e.$$S(m)=4S(m/2)-\log m\tag{..2}$$ thereby $$S(m)=4^2S(\frac{m}{2^2})-4\log \frac{m}{2}-\log m\implies S(m)=4^2S(\frac{m}{2^2})-\left(\log\frac{m^{4^0+4^1}}{2^{0\times4^0+1\times 4^1}}\right)$$ Generalization:- $$\implies S(m)=4^kS\left(\frac{m}{2^k}\right)-\left(log\frac{m^{4^0+.....4^{k-1}}}{2^{0\times4^0+....+(k-1)\times4^k}}\right)$$ Now we have sum of n terms of geometric progression:- $$S_G=a\frac{r^{n}-1}{r-1}\tag{...3}$$ and sum of n terms of arithmetico - geometric progression:- $$S_{AG}=\frac{a}{1-r}+\frac{dr(1-r^{n-1})}{(1-r)^2}-\frac{(a+(n-1)d)r^n}{1-r}\tag{..4}$$ From eq.(3.) and (4.)

$$\implies S(m)=4^kS\left(\frac{m}{2^k}\right)-\left(\log\frac{m^\frac{4^k-1}{3}}{2^{\frac{4^{k+1}-3k4^k-4}{9}}}\right)$$ If $S(1)=1$ .i.e $k=\log_2 m$ and Since $n=\log_2 m \implies m=2^n $ & $n=k$ $$\implies S(m)=4^kS\left(\frac{m}{2^k}\right)-n\frac{4^k-1}{3}+\frac{4^{k+1}-3k4^k-4}{9}$$ $$\implies T(n)=5\times 4^n-6n4^n+3n-4\implies T(n)=\theta (4^n)$$