Solving the recurrence relation $T(n)=4T(n-1)+n+1, T(0)=1$

Question

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?

Answer 1

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}$$

Answer 2

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$.