Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
Thank you! I'm understanding what to do with these types of problems a bit more now. –  Lish Sep 30 '11 at 18:18
2  
@Andre: (+1) for rolling up your sleeves and working the problem assuming no backgound. However, I try to avoid answering the whole of a homework problem. –  robjohn Sep 30 '11 at 18:27
2  
@robjohn: Agreed, and I would have been more cryptic, at least in the first round, if I had noticed it was homework. But ordinarily I am not even aware of tags. I am hoping that at least there will be two small lessons learned by the OP: (i) Calculate! (ii) A commonsense proof technique for showing that a "guessed" answer is correct. –  André Nicolas Sep 30 '11 at 18:40
2  
@André: I, too, have answered homework problems too well before being notified it was a homework problem. I wouldn't have upvoted if I didn't think it was a good answer anyway. –  robjohn Sep 30 '11 at 19:03
add comment

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

share|improve this answer
2  
+1 for going general. –  Arjang Feb 25 '13 at 22:20
add comment

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.