We suppose that $S(k)$ is true for $k>2$, and we prove $S(k+1)$ is true. That is, we suppose that for a fixed $k$ there is a polynomial $T_k(x)$ such that $$G_{2^kr}^{*}(x)= G_{r}^{*}(x)T_k(x)+(2/\alpha)g^{2^{k-1}r}(x).$$ From part (1) we have $G_{2^{k+1}r}^{*}(x)= G_{2^k r+2^k r}^{*}(x)=\alpha(G_{2^k r}^{*}(x))^2-(2/\alpha)(g(x))^{2^k r}$. Using the result from the inductive hypothesis $S(k)$ and simplifying, we obtain $$\begin{aligned}
G_{2^{k+1}r}^{*}(x)&=&\alpha[ G_{r}^{*}(x)T_k(x)+\frac{2}{\alpha}(g(x))^{2^{k-1} r} ]^2-\frac{2}{\alpha}(g(x))^{2^k r}\\
&=&G_{r}^{*}(x)[\alpha G_{r}^{*}(x)T_k ^2(x)+4T_k(x)(g(x))^{2^{k-1} r} ]+\frac{4}{\alpha}(g(x))^{2^k r} -\frac{2}{\alpha}(g(x))^{2^kr}\\
&=&G_{r}^{*}(x)T_{k+1}(x)+\frac{2}{\alpha}(g(x))^{2^kr},\end{aligned}$$ where $T_{k+1}(x)=\alpha G_{r}^{*}(x)T_k ^2(x)+4T_k(x)(g(x))^{2^{k-1} r} $. This completes the proof of part (3).

In the following part of this section, we present two divisibility properties for the GFP.

\[divisity:property:fibonacci\] If $\{ G_{n}^{'}(x)\}$ is a GFP sequence of the Fibonacci type, then $G_{m}^{'}(x)$ divides $G_{n}^{'}(x)$ if and only if $m$ divides $n$.

We first prove the sufficiency. Based on the hypothesis that $m$ divides $n$, there is an integer $q\ge1$ such that $n=mq$. Then, using the Binet formula (\[bineformulauno\]), we have that,

$$G_{m}^{'}(x)=(a^m-b^m)/(a-b)\,\, \text{  and  }\,\, G_{mq}^{'}(x)=(a^{mq}-b^{mq})/(a-b).$$

It is easy to see –using induction on $q$– that $(a^m-b^m)$ divides $(a^{mq}-b^{mq})$ which implies that $G_{m}^{'}(x)$ divides $G_{mq}^{'}(x)$. This proves the sufficiency.

We now prove the necessity. Suppose that $m$ does not divide $n$ and that $G_{m}^{'}(x)$ divides $G_{n}^{'}(x)$ for $m$ and $n$ greater 