# Thread: Recurrence relation

1. ## Recurrence relation

The sequence {a_n} = 1,11,41,131,401,... satisfies the relation
a_(n+2) = 4*a_(n+1) - 3*a_n for n>=0. Find a const. coefficient, linear, homogeneous recurrence relation(of smallest order) which is satisfied by the sequence
(1)^2,,(11)^2,(41)^2,(131)^2,... = 1,121,1681,17161,... .

The characteristic equation for the given relation is x^2 - 4*x + 3 = 0. The roots for this equation are 3 and 1. Imposing the values of a_0 and a_1, we find that a_n = 5*(3^n) - 4. Here is the point i don't know what to do next.

2. Originally Posted by hastings
The sequence {a_n} = 1,11,41,131,401,... satisfies the relation
a_(n+2) = 4*a_(n+1) - 3*a_n for n>=0. Find a const. coefficient, linear, homogeneous recurrence relation(of smallest order) which is satisfied by the sequence
(1)^2,,(11)^2,(41)^2,(131)^2,... = 1,121,1681,17161,... .

The characteristic equation for the given relation is x^2 - 4*x + 3 = 0. The roots for this equation are 3 and 1. Imposing the values of a_0 and a_1, we find that a_n = 5*(3^n) - 4. Here is the point i don't know what to do next.
If $\displaystyle a_n = 5\times3^n - 4$ then $\displaystyle a_n^2 = 25\times 9^n - 20\times3^n + 16$. Now suppose that $\displaystyle a_{n+3}^2 = pa_{n+2}^2 + qa_{n+1}^2 + ra_n^2$. Since
$\displaystyle a_{n+3}^2 = 25\times 9^{n+3} - 20\times3^{n+3} + 16$,
$\displaystyle a_{n+2}^2 = 25\times 9^{n+2} - 20\times3^{n+2} + 16$ and
$\displaystyle a_{n+1}^2 = 25\times 9^{n+1} - 20\times3^{n+1} + 16$,
we can compare coefficients of 9^n, 3^n and the constant terms, in the equation $\displaystyle a_{n+3}^2 = pa_{n+2}^2 + qa_{n+1}^2 + ra_n^2$. This gives a set of linear equations for p, q and r, namely
$\displaystyle 81p+9q+r=729$,
$\displaystyle 9p+3q+r=27$,
$\displaystyle p+q+r=1$.

If I haven't made a careless mistake, the solution to these equations gives the result $\displaystyle a_{n+3}^2 = 13a_{n+2}^2 - 39a_{n+1}^2 + 27a_n^2$. This is certainly a constant coefficient, linear, homogeneous recurrence relation which is satisfied by the given sequence. BUT I'm not sure whether it is the one of smallest order. (I guess that it must be.)

3. Thanks Opalg. I went through all the steps you proceeded, and found the same result. Assuming a third order recurrence relation was clever and i'm convinced that this is of smallest possible order because i imitated the same result for a second order relation but didn't come up with a reasonable answer.