If $T(0) = 0$ and $T(n>0) = 2T(n-1)+4^n+1$, what is the explicit formula (via recursion)?

Question

All I know is that you'd have to use substitution to get rid of $T(n-1)$ and summations for the rest, but whenever I work through it I get to $2^{(n+2)}+2^{(n-1)}-2.5$ which is not the correct answer (checked via excel).

Answer 1

At each step, replace $n$ with $n - 1$ and multiply the equation by $2$: \begin{align*} T(n) - 2T(n - 1) &= 2^{2n} + 1 \\ 2T(n - 1) - 2^2T(n - 2) &= 2^{2n-1} + 2 \\ 2^2T(n - 2) - 2^3T(n - 3) &= 2^{2n - 2} + 2^2 \\ 2^3T(n - 3) - 2^4T(n - 4) &= 2^{2n - 3} + 2^3 \\ &~~\vdots \\ 2^{n-1}T(1) - 2^nT(0) &= 2^{n + 1} + 2^{n-1} \\ \end{align*} Summing the $n$ equations together, notice that the LHS telescopes, yielding: \begin{align*} T(n) - 2^nT(0) &= (1 + 2 + 2^2 + \cdots + 2^{n-1}) + (2^{n+1} + 2^{n+2} + \cdots + 2^{2n}) \\ T(n) - 2^n(0) &= \left[\sum_{k=0}^{2n} 2^k\right] - 2^n\\ T(n) &= 2^{2n + 1} - 1 - 2^n \end{align*}

Answer 2

First off, "$T(n\gt0)=2T(n-2)+4^n+1$" does not parse. I'm going to guess you meant to say that $T(n)=2T(n-2)+4^n+1$ when $n\gt0$.

The general solution of the corresponding homogeneous equation $T(n)=2T(n-1)$ is obviously $T(n)=c\cdot2^n$.

Next, considering the input function is $4^n+1$, we "guess" that the original nonhomogeneous equation has a solution of the form $T(n)=A\cdot4^n+B$. Plugging this into the recurrence equation and equating coefficients, we get $A=2,B=-1$; so we have a particular solution $T(n)=2\cdot4^n-1$, and the general solution is $$T(n)=2\cdot4^n-1+c\cdot2^n.$$ Settint $n=0$, your initial value $T(0)=0$ leads to $c=-1$, so the final answer is $$T(n)=2\cdot4^n-1-2^n=2^{2n+1}-2^n-1.$$