Continued Fraction Recursion: Loose Ends

[Leroy Quet]

On 2/27/07, Max Alekseyev <maxale at gmail.com> wrote:
> On 2/27/07, Tanya Khovanova <tanyakh at tanyakhovanova.com> wrote:
> >
> > >
> > >Nice work! Do you consider more general second order recurrences:
> > >a(n) = c_1 * a(n-1) + c_2 * a(n-2)
> > >and the inhomogenous case:
> > >a(n) = c_1 * a(n-1) + c_2 * a(n-2) + b(n)?
> > >
> >
> > Thank you! I would like to expand my webpage. Unfortunately for me and fortunately for humanity OEIS has too many sequences. :-) For the page I did, I had to check and copy manually more than 1,000 sequences.
>
> Actually, it is easy to detect Lucas sequences algorithmically:
>
> For any 5 consecutive terms of such a sequence t1, t2, t3, t4, t5 the
> determinant
>
> | t1 t2 t3 |
> | t2 t3 t4 | must be 0.
> | t3 t4 t5 |
>
> If at least one of the determinants is non-zero, implies that the
> sequence is not Lucas one. So, a simple program can easily filter out
> most of the non-Lucas sequences.

Similarly, in the inhomogenous case with a constant trailing term:
a(n) = c_1 * a(n-1) + c_2 * a(n-2) + b
for any 6 consecutive elements t1, t2, t3, t4, t5, t6 the determinant:

| t2-t1 t3-t2 t4-t3 |
| t3-t2 t4-t3 t5-t4 | must be 0.
| t4-t3 t5-t4 t6-t5 |

This can be extended further to detecting b(n) being a polynomial of a
bounded degree.

Max