Comments on A122046
A. N. W. Hone, Jul 15 2008

The exact formula for the terms d_n of A122046, which are the degrees of the polynomials
generated by the quadratic recurrence

P_{n}P_{n-5}= x^{n-1}P_{n-1}P_{n-4}+P_{n-2}P{n-3} -----(*)

with the five initial values P_{-3}=...=P_1=1, is

d_n = \frac{1}{4\sqrt{2}}\cos((2n+1)\pi / 4)+\frac{1}{96}(2n+3)(2n^2+6n-5)+\frac{1}{32}(-1)^n.

This comes from the fact that the degrees d_n satisfy the 7th order homogeneous linear recurrence

(S-1)^4(S+1)(S^2+1)d_n=0

(where S is the shift operator, i.e. Sf_n =f_{n+1}) and the seven initial values for this are
d_{-3}=...=d_1=0 and d_2=1,d_3=3.

The proof is as follows:

Assume that (*) with five initial 1s generates a sequence of polynomials in x (see note below).

Then from (*) it follows that the degrees of the polynomials satisfy the 5th order recurrence

d_{n}+d_{n-5} = max \{ n-1 + d_{n-1}+d_{n-4},d_{n-2}+d_{n-3} \}

(with 5 zeros as initial data: d_{-3}=...=d_1=0).

Letting v_n =  d_n+d_{n-3}-d_{n-1}-d_{n-2} this becomes the second order recurrence

v_n+v_{n-2}=\max { n-1, - v_{n-1} \}   ---(**)

with initial values v_0=v_1=0. By induction it is easy to see that v_n is non-negative and
satisfies

v_n + v_{n-2} = n-1

for all n \geq 2 (so the first term on the r.h.s. of (**)  is always the largest).
This is equivalent to a 5th order linear inhomogeneous recurrence for the degrees
d_n (whose consequence is the 7th order homogeneous linear recurrence given above),
and the explicit formula for d_n then follows.

Note: Richard Mathar has alerted me to the fact that apparently no proof has been given that the
recurrence (*) introduced by Roger Bagula does indeed produce polynomials in x. The recurrence (*) is a non-autonomous version of the Somos-5 recurrence, and the fact that it generates
polynomials is a generalisation of the Laurent phenomenon studied by Fomin & Zelevisnky in
their work on cluster algebras. However, their methods to not apply directly here. Nevertheless,
I think it would be fairly easy to prove the Laurent property for (*) directly by induction.