1
$\begingroup$

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!

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – guest
    Feb 14, 2014 at 6:48
  • $\begingroup$ 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. $\endgroup$ Feb 14, 2014 at 6:53
  • $\begingroup$ 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)$? $\endgroup$
    – guest
    Feb 14, 2014 at 7:09
  • $\begingroup$ Forget the $a$'s when you work the $c$'s $\endgroup$ Feb 14, 2014 at 7:14
  • $\begingroup$ 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$? $\endgroup$
    – guest
    Feb 14, 2014 at 7:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .