# Math Help - 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 $a_n = 5\times3^n - 4$ then $a_n^2 = 25\times 9^n - 20\times3^n + 16$. Now suppose that $a_{n+3}^2 = pa_{n+2}^2 + qa_{n+1}^2 + ra_n^2$. Since
$a_{n+3}^2 = 25\times 9^{n+3} - 20\times3^{n+3} + 16$,
$a_{n+2}^2 = 25\times 9^{n+2} - 20\times3^{n+2} + 16$ and
$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 $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
$81p+9q+r=729$,
$9p+3q+r=27$,
$p+q+r=1$.

If I haven't made a careless mistake, the solution to these equations gives the result $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.