Solving Recurrence Relation 5

Question

How to solve the recurrence relation given by the equation below

$$T(n)=T(n-2)+T(n-4)+T(n-6)+...+T(0)$$

It seems to me that $T(n)$ will be exponential but i don't know how to proceed on this problem.

Answer 1

Hint:

$T_2=T_0$

$T_4=T_2+T_0=2T_0$

$T_6=T_4+T_2+T_0=2T_4=2^2T_0$

.

.

$T_n=2T_{n-2}=2^{\frac{n}{2}-1}T_0$

Answer 2

Let $T(0)$=1, then $T(2)=1=2^0$, $T(4)=2=2^1$, $T(6)=4=2^2$, $T(8)=8=2^3$.

Answer 3

Hint: $T(n-2)=T(n-4)+T(n-6)+T(n-8)+...T(0)$

Answer 4

Let $S(k) = T(2 k).$ Then $S(n) = \sum_{k=0}^{n-1} S(k),$ which will grow exponentially with base $2.$

Similarly, define $R(k) = T(2k+1).$ This will satisfy the same recurrence, with the same solution, so your thing grows like $2^{n/2}.$

Answer 5

You can turn the given recurrence in a more traditional form:

$$T(n+2)=\color{green}{T(n)}+\color{blue}{T(n-2)+T(n-4)+T(n-6)+...+T(0)}=\color{green}{T(n)}+\color{blue}{T(n)}.$$

The solution is obviously

$$T(n)=C2^{n/2}$$ for even, positive $n$.

With the initial condition

$$T(2)=T(0),$$

we have $$T(n)=2^{n/2-1}T(0)$$ where $T(0)$ is assumed to be known.