2
$\begingroup$

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.

  • 0
    I'm trying to, but it's the most incredibly confusing text I've ever read.2011-09-30

3 Answers 3

8

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. 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.

  • 0
    Thank you! I'm understanding what to do with these types of problems a bit more now.2011-09-30
3

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

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?

  • 0
    Luckily (or unluckily, depending on how you look at it), the characteristic polynomial has a double root...2011-09-30