# Solve $t_{n}=t_{n-1}+t_{n-3}-t_{n-4}$?

I missed the lectures on how to solve this, and it's really kicking my butt. Could you help me out with solving this?

Solve the following recurrence exactly. $$t_n = \begin{cases} n, &\text{if } n=0,1,2,3, \\ t_{n-1}+t_{n-3}-t_{n-4}, &\text{otherwise.} \end{cases}$$ Express your answer as simply as possible using the $\Theta$ notation.

-
Do you have a text to read up in, even if you missed the lecture? If so you should be able to show some more work than just reproducing the question. – Henning Makholm Sep 30 '11 at 17:25
I'm trying to, but it's the most incredibly confusing text I've ever read. – Lish Sep 30 '11 at 17:28

I do not know at what stage you are in dealing with linear recurrences with constant coefficients, and in particular whether you already have general tools.

If you do not yet have general tools for recurrences of this kind, and even if you do, it may be useful to compute a few more terms, in order to get additional insight about the sequence $(t_n)$.

We have $t_4=t_3+(t_1-t_0)=3+(1-0)=4$.

Also, $t_5=t_4+(t_2-t_1)=5$.

Also, $t_6=t_5+(t_3-t_2)=6$.

Also, $t_7=t_6 +(t_4-t_3)=7.$

The pattern is hard to miss! Now let us prove that the pattern always holds. An easy way to do this is to define the sequence $(s_n)$ by $s_n=n$. We want to show that $t_n=s_n$ for all $n$.

It is easy to verify that $$s_n=s_{n-1}+s_{n-3}-s_{n-4}$$ for all $n$, since $n-1+n-3-(n-4)=n$. Also, $s_n=n$ for $n=0, 1, 2, 3$. Of course.

So the sequence $(s_n)$ obeys the same recurrence as $(t_n)$, and the same initial conditions. The two sequences are therefore identical.

Or else we can do a formal proof by induction that $t_n=n$ for all $n$.
The induction step is as follows. Suppose that $t_k=k$ for all $k<n$. We want to show that $t_n=n$. We are given that $$t_n=t_{n-1}+t_{n-3}-t_{n-4}.$$ By induction hypothesis, $t_{n-1}=n-1$, $t_{n-3}=n-3$, and $t_{n-4}=n-4$. Calculate. We get that $t_n=n-1+ n-3 -(n-4)=n$. Note that this is fundamentally the same argument as the first one.

-
Thank you! I'm understanding what to do with these types of problems a bit more now. – Lish Sep 30 '11 at 18:18

Let's tackle it the general way. Define the ordinary generating function: $$T(z) = \sum_{n \ge 0} t_n z^n$$ Writing the recurrence as $t_{n + 4} = t_{n + 3} + t_{n + 1} - t_n$, the properties of ordinary generating functions give: \begin{align*} \frac{T(z) - t_0 - t_1 z - t_2 z^2 - t_3 z^3}{z^4} &= \frac{T(z) - t_0 - t_1 z - t_2 z^2}{z^3} + \frac{T(z) - t_0}{z} - T(z) \\ T(z) &= \frac{z}{(1 - z)^2} \end{align*} This has the coefficient: $$t_n = [z^n] \frac{z}{(1 - z)^2} = [z^{n - 1}] \frac{1}{(1 - z)^2} = (-1)^{n - 1} \binom{-2}{n - 1} = n$$

-
+1 for going general. – Arjang Feb 25 '13 at 22:20

Hint:

Write $t_n = r^n$, substitute into the definition of $t_n$ for $n>3$ and solve for $r$. You will find four possible solutions. Call them $r_1$, $r_2$, $r_3$ and $r_4$. Because the defining equation is linear, you can write

$$t_n = A r_1^n + B r_2^n + C r_3^n + D r_4^n$$

Now how can you work out what the constants $A$, $B$, $C$, $D$ are?

-
I'm not understanding how to solve these for r to get multiple solutions... This isn't really something I've done before. – Lish Sep 30 '11 at 17:34
@Lish: if you're going to be working more of these types of problems later, this is the way to work them in general. Your problem happened to work out very simply because the initial values were tailor-made, and the more general terms of the general solution were suppressed. – robjohn Sep 30 '11 at 18:26
The general solution of this recursion is not a sum of four exponentials. – zyx Sep 30 '11 at 18:47
Luckily (or unluckily, depending on how you look at it), the characteristic polynomial has a double root... – J. M. Sep 30 '11 at 22:16