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.
Asked
Active
Viewed 63 times
1
-
What are $T(0)$ and $T(1)$? – k99731 Jan 03 '17 at 07:45
-
2You can simplify the above as $T_n=2T_{n-2}$ – 8hantanu Jan 03 '17 at 07:48
-
Your recurrence only works for $n$ even. You should also provide one for $n$ odd. – Alex M. Jan 03 '17 at 09:50
5 Answers
0
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$
8hantanu
- 1,843
0
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.
-1
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}.$
Igor Rivin
- 25,994
- 1
- 19
- 40
-
You have no information about the values at odd numbers, there is nothing you can deduce. – Jan 03 '17 at 08:39
-
@YvesDaoust Why don't I have information about the values at odd numbers? Because you have reading comprehension issues? – Igor Rivin Jan 03 '17 at 09:41
-
-
@YvesDaoust The OP says nothing about initial conditions of any kind, so what do you know abut $T(0)?$ Or $T(2)?$ – Igor Rivin Jan 03 '17 at 10:39
-
The recurrence says $T(2)=T(0)$. There is no equivalent for odd terms. Unless you read a different text than me. – Jan 03 '17 at 10:47