Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ 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?

 A: 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)$. 
A: 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)$$
