3 Sequences of squared terms

3.1 A 3-dimensional space

Let us now consider the set of all the squared terms sequences associated to a sequence . From Eq. 5, we have and therefore is a subset of the vector space generated by the geometric sequences , and . This 3-dimension vector space is the set of the sequences verifying the recurrence relation of third order whose characteristic polynomial is namely

The generating function of such a sequence has therefore the form

and it can be checked that the sequences defined in Eq. 3 are described by :

Sequence	U	V	W

Proposition 3  

When recurrence Eq. 4 is really a recurrence of second order (i.e. and ), the vector space is spanned by , , if and only if vector space is spanned by .

Proof. Compute the determinant of and obtain .

3.2 Even and odd subsequences

Let us now consider the even and odd subsequences and defined by and . In the general case, their generating functions can be obtained by

but here, we have obviously :

Being expandable in the geometric basis, both and belong to the vector space and therefore are expandable in the basis. Going back from generating function to the corresponding sequences, we obtain  :

Theorem 1  

Let be a non-geometric sequence verifying a linear recurrence of second order. Let be the roots of the characteristic polynomial. Then for all  :

In equation Eq. 16, the quantities and were only introduced to obtain more "cosmetic" formulae. When eliminating the cross term (and re expanding and ), a nice formula is obtained :

Theorem 2  

When verifies the hypotheses of thm:even-odd then, for all  :

In the genuine Fibonacci case, this result is the formerly stated relation Eq. 2.

3.3 Essentially different relations cannot be found

In order to see if other relations of this kind can be found, we have to understand why relation Eq. 17 holds. On the left side, we have a linear combination of squared terms. The poles involved in the corresponding generating function are . On the right side, we have a combination of terms coming from "arithmetic subsequences", i.e. . But, from Eq. 5, we have :

Proposition 4  

For fixed , all the arithmetic subsequences obey to the same linear recurrence of order 2, whose poles are and .

The only way to have the same poles on both sides is to use only (the odd and even sub-series) on the right, and to avoid the pole on the left. Therefore this left side must embed an action that results in the apparition of the factor in the generating function. But this factor codes for the action acting over sequences: the left member is necessarily a linear combination of the sequences obtained by shifting the sequence .

Applied to the (genuine) Fibonacci sequence, this proves that the only combination of squares that can be linearized are those build upon by shifts and linear combinations. For example, the expression , whose generating function is

cannot be linearized due to the presence of pole .