Problem

[Max Alekseyev]

On Nov 16, 2007 12:10 PM, Max Alekseyev <maxale at gmail.com> wrote:

> You can describe their union as the following 6th order recurrent sequence:
> n(j) = 18*n(j-3) - n(j-6)
> with
> n(0)=1, n(1)=4, n(2)=11, n(3)=29, n(4)=76, n(5)=199.

Oh, it turns out that this can be reduced to the second order
recurrence (as noticed by Zak Seidov).
The characteristic polynomial here has the following factorization:

t^6 - 18 t^3 + 1 = (t^2 - 3t + 1) * (t^4 + 3 t^3 + 8 t^2 + 3 t + 1)

and the initial conditions are well consistent with the first factor
t^2 - 3t + 1. Therefore, our sequence also satisfies a simpler
recurrence:
n(j) = 3*n(j-1) - n(j-2)
with
n(0)=1, n(1)=4.

Max