# Finding a recurrence for $c_n=a_{n+1}-a_n$ provided that $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$

Suppose $$a_0,a_1,a_2$$ satisfy the recurrence $$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$$ for $$n\ge3$$.

Let $$c_n=a_{n+1}-a_n$$ for $$n\ge1$$ and $$c_0=0$$.

Find a linear recurrence of degree at most $$2$$ for the sequence $$c_0,c_1,c_2,\dots$$.

I'm not entirely sure what they are asking for but I think it is asking for a recurrence relation for $$c_n$$ where the characteristic polynomial has degree at most $$2$$.

I tried finding a closed form for $$a_n$$ to try and get rid of the $$a_n$$ in the $$c_n$$ equation, but I can't figure it out when the initial conditions aren't specified ($$a_0,a_1,a_2$$).

Any help would be appreciated!

Here is a start. First shift the index, then rearrange as $$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3} \implies a_{n+1} = 3a_{n}-3a_{n-1}+a_{n-2}$$

$$\implies a_{n+1} - a_n= 2(a_{n}-a_{n-1})-(a_{n-1}-a_{n-2})$$

Now, use $c_n= a_{n+1}-a_n$ in the last equation to get a recurrence relation of degree $2$ in terms of $c_n$. I think you can finish it.

Hint

More empirically than Mhenni Benghorbal, you can assume that you know the first terms of $a(n)$ (just name them $a_0$,$a_1$ and $a_2$). The condition $c(0)=0$ shows that $a_0=a_1$. Compute a very few terms for $a(n)$ and $c(n)$. The pattern becomes obvious.

• when I try to compute things they all end up as $0$. Is this the pattern you were hinting at, or am I way off? Feb 14, 2014 at 6:48
• You must have something wrong. What I obtained is $c(1)=a_2 -a_1$, $c(2)=2(a_2 -a_1)$, $c(3)=3(a_2-a_1)$ and so on. Feb 14, 2014 at 6:53
• If I say that $a_0=a_1$ then when I try to compute $a_2$ I get $a_2=3a_1-3a_0$ which makes $a_2=0$. How are you getting $c(2)=2(a_2 -a_1)$? Feb 14, 2014 at 7:09
• Forget the $a$'s when you work the $c$'s Feb 14, 2014 at 7:14
• Ok I can see where $c(2)=2(a_2 -a_1)$ comes from now. How does this help find the recurrence relation for $c_n$ when I still don't know any of the $a_i$? Feb 14, 2014 at 7:23