Solving the recurrence relation $T(n)=4T(n-1)+n+1, T(0)=1$ I'm attempting to solve the recurrence relation 
$ T(n)=4T(n-1)+n+1, T(0)=1 $
From here I say 
$ T(n-1) = 4(4T(n-2)+n)+n+1 = 4^2T(n-2)+4n+n+1 $
$ = 4^2(4T(n-3)+n-1)+4n+n+1 = 4^3T(n-3)+(4^2+4+1)n-4^2+1 $
At this point, I understand most of the pattern. I see this as 
$ 4^n + (4^n + ... + 4^1 + 4^0)n + something $
I don't know how to generalize the last part. I also don't know where to go with the coefficient of $n$. Can anyone help? 
 A: Step 1: The homogeneous recurrence is $T(n)=4T(n-1)$, which has general solution $T(n)=A4^n$.
Step 2: To take care of the nonhomogeneous version, we need a single solution.  I guess a linear solution $T(n)=Bn+C$.  We plug into the recurrence to get $$Bn+C=4(B(n-1)+C))+n+1$$
Collecting terms we get $$Bn+C=(4B+1)n+(-4B+4C+1)$$
This gives us equations $B=4B+1, C=-4B+4C+1$, which has solution $B=-\frac{1}{3}, C=-\frac{7}{9}$.  
Step 3: The general solution to the nonhomogeneous recurrence is the sum of the previous, namely $$T(n)=A4^n-\frac{1}{3}n-\frac{7}{9}$$
Now we are ready for the initial condition, to find $A$.  We have $$1=T(0)=A4^0-\frac{7}{9}$$
So $A=\frac{16}{9}$.  Putting it all together, the solution we seek is $$T(n)=\frac{16}{9}4^n-\frac{1}{3}n-\frac{7}{9}$$
A: Assume that the domain of $T$ can be extended to the reals and that $T$ is twice differentiable. Differentiating the original equation twice gives $T''(x)=4 T''(x-1)$, which by inspection has a solution $T''(x)= 4^x A$ with constant $A$. Integrating twice gives $T(x)=4^x A^*+x B +C$ where $A^*=A(\ln 4)^{-2}$, and $B,C$ are constants.The conditions of the original equation , and $T(0)=1$, are sufficient to find $A^*,B,C$......To show that the solution is unique, suppose that $T,U$ are solutions with $T(0)=U(0).$ Then let $V=T-U$. We have $V(n)=4V(n-1)$ with $V(0)=0$. So by induction on $n$ we have $V(n)=0$ for all $n$.That is,  $T=U$.
