Solving $ T(n) = 1 + 2( T(n-2) + T(n-3) +\cdots+T(0) ) $

Question

I have the following recurrence relation which I have obtained from an algorithm:

$$ T(n) = 1 + 2( T(n-2) + T(n-3)+\cdots+T(0) ) $$

with base case $T(0) = 1$ and $ T(1) = 1 $

I would like to be able to compute an analytic formula for this as the inputs for this are too big to just compute it with a for loop (even with keeping track of the computation already made).

I tried drawing the recursion tree but I get stuck.

Ideas? :)

Answer 1

How about this idea:

Since $T(n) = 1 + 2(T(n-2) + T(n-3) + \dots + T(0))$ and $T(n-1) = 1 + 2(T(n-3) + T(n-4) + \dots + T(0))$.

Therefore $T(n) = T(n-1) + 2T(n-2)$.

Can you solve this new recursion?

Answer 2

First observe what occurs when working with finite differences:$$\begin{align*}T(n)&=1+2\sum_{k=0}^{n-2} T(k)\\T(n+1)&=1+2\sum_{k=0}^{n-1}T(k)\\&=1+2T(n-1)+2\sum_{k=0}^{n-2}T(k)\\T(n+1)-T(n)&=2T(n-1)\\T(n+1)&=T(n)+2T(n-1)\\T(n)&=T(n-1)+2T(n-2)\end{align*}$$Now assume $T(n)=r^n$ is a solution to the above linear homogeneous recurrence relation. We have:$$\begin{align*}r^n&=r^{n-1}+2r^{n-2}\\r^2&=r+2\\r^2-r-2&=0\\(r-2)(r+1)&=0\end{align*}$$hence $2^n,(-1)^n$ generate all solutions i.e. the general solution is $T(n)=A2^n+B(-1)^n$. Our initial conditions $T(0)=1,T(1)=1$ gives us:$$T(0)=A2^0+B(-1)^0\\1=A+B$$and$$T(1)=2A-B\\1=2A-B$$so $A=\dfrac23,B=\dfrac13$ and our solution is given by the explicit formula$$T(n)=\frac23 2^n+\frac13 (-1)^n=\frac13(2^{n+1}+(-1)^n)$$