Derive homogeneous recurrence from second order one

Let's use the characteristic function of the recurrence sequence. It is $\lambda^2-a\lambda+b^2=0$. Let's assume it has two distinct root $\lambda_1,\lambda_2$. This is without loss of generality, since the set $\{(a,b)\in\mathbb R^2:a^2-4b^2\ne 0\}$ is dense, and we are looking for some identity, which is just some polynomials in $a,b$ after expansion. Then $$ f(n)=x\lambda_1^n+y\lambda_2^n. $$

Let $\zeta_k=e^{2\pi i/k}$. Note the sequence $$ \chi_k(n):=\frac{1+\zeta_k^n+\zeta_k^{2n}+\dots+\zeta_k^{(k-1)n}}{k}=\begin{cases} 1& k|n\\ 0& \text{else} \end{cases}. $$ If $n=km+r$, then $m=(n-r)/k$, and $$ f_k(n)=f(m+1)^rf(m)^{k-r}=f\left(\frac{n+k-r}{k}\right)^rf\left(\frac{n-r}{k}\right)^{k-r}. $$ We use $\chi_k(n)$ to put them together. For each $r=0,1,\dots,k-1$, $n=km+r\iff \chi_k(n-r)=1$, so $$ f_k(n)=\sum_{r=0}^{k-1}f\left(\frac{n+k-r}{k}\right)^rf\left(\frac{n-r}{k}\right)^{k-r}\chi_k(n-r). $$ To avoid multi-valuedness of complex $k$-th root, we find a particular $k$-th root of $\lambda_1$ and $\lambda_2$, call them $\lambda_1^{1/k},\lambda_2^{1/k}$, and fix them throughout the rest of this proof. We denote $C$ to be the set of constants not related to $n$ but possibly related to $\lambda_1,\lambda_2, r,k$. Then $$ f\left(\frac{n+k-r}{k}\right),f\left(\frac{n-r}{k}\right)\in \lambda_1^{n/k}C+\lambda_2^{n/k}C. $$ $$ \chi_k(n-r)\in \zeta_k^{0n}C+\zeta_k^{1n}C+\zeta_k^{2n}C+\dots+\zeta_k^{(k-1)n}C. $$ These combined, we know $$ f\left(\frac{n+k-r}{k}\right)^rf\left(\frac{n-r}{k}\right)^{k-r}\chi_k(n-r)\in \sum_{0\le j\le k,0\le l\le k-1} \lambda_1^{jn/k}\lambda_2^{(k-j)n/k}\zeta_k^{ln}C. $$ Summing it up, we conclude that $$ f_k(n)=\sum_{r=0}^{k-1}f\left(\frac{n+k-r}{k}\right)^rf\left(\frac{n-r}{k}\right)^{k-r}\chi_k(n-r)\in \sum_{0\le j\le k,0\le l\le k-1} \lambda_1^{jn/k}\lambda_2^{(k-j)n/k}\zeta_k^{ln}C. $$ It's a homogeneous polynomial in $\lambda_1^{n/k},\lambda_2^{n/k}$ of degree k. Let's consider the first term, i.e., the term with $(\lambda_1^{n/k})^k(\lambda_0^{n/k})^0=\lambda_1^n$ in it. Clearly, all the summand in $$ f\left(\frac{n+k-r}{k}\right)^rf\left(\frac{n-r}{k}\right)^{k-r}=\left(x\lambda_1^\frac{n+k-r}{k}+y\lambda_2^\frac{n+k-r}{k}\right)^r\left(x\lambda_1^\frac{n-r}{k}+y\lambda_2^\frac{n-r}{k}\right)^{k-r} $$ should take the $\lambda_1$ term.

So $$ [(\lambda_1^{n/k})^k(\lambda_0^{n/k})^0]f_k(n)=\sum_{r=0}^{k-1}x^rx^{k-r}\chi_k(n-r)=x^k\sum_{r=0}^{k-1}\chi_k(n-r)=x^k. $$ This means, the coefficient of $(\lambda_1^{n/k})^k(\lambda_0^{n/k})^0=\lambda_1^n$ does not contain anything in the form of $\zeta_k^{ln},l\ne 0$. Same arguments apply to the term $\lambda_2^n$.

We refine our result as $$ f_k(n)=\sum_{r=0}^{k-1}f\left(\frac{n+k-r}{k}\right)^rf\left(\frac{n-r}{k}\right)^{k-r}\chi_k(n-r)\in \sum_{0< j< k,0\le l\le k-1} \lambda_1^{jn/k}\lambda_2^{(k-j)n/k}\zeta_k^{ln}C+\lambda_1^nC+\lambda_2^nC. $$ We read off the roots of the characteristic function of $f_k(n)$ from this, and its characteristic function should be $$ F_k(\lambda)=(\lambda-\lambda_1)(\lambda-\lambda_2)\prod_{0< j< k,0\le l\le k-1}(\lambda-\lambda_1^{j/k}\lambda_2^{(k-j)/k}\zeta_k^{l}). $$ We use the identity $$ \prod_{0\le l\le k-1}(A-B\zeta_k^{l})=A^k-B^k, $$ so $$ F_k(\lambda)=(\lambda-\lambda_1)(\lambda-\lambda_2)\prod_{0< j< k}(\lambda^k-\lambda_1^{j}\lambda_2^{k-j}). $$

The following Mathematica code can calculate the coefficients of the recurrence relation of $f_k(n)$. For each given $k$, it calculate the characteristic function, and put the coefficients in descending order in $\lambda$ into a list. We can see the $k=2,3,4$ cases match with your results.

In[152]:= (*I denote the λ by l here*)

In[153]:= 
polyF[k_] := -Product[(l^k - l1^j l2^(k - j)), {j, 1, k - 1}] (l - 
    l1) (l - l2)

In[154]:= 
solve[k_] := 
  Reverse@CoefficientList[
    SymmetricReduction[polyF[k], {l1, l2}, {a, b^2}] // First, l];

In[155]:= solve[2]

Out[155]= {-1, a, 0, -a b^2, b^4}

In[156]:= solve[3]

Out[156]= {-1, a, -b^2, a b^2, -a^2 b^2, a b^4, -b^6, a b^6, -b^8}

In[157]:= solve[4]

Out[157]= {-1, a, -b^2, 0, a^2 b^2 - b^4, -a^3 b^2 + a b^4, 
 a^2 b^4 - b^6, 0, -a^2 b^6 + b^8, 
 a^3 b^6 - a b^8, -a^2 b^8 + b^10, 0, b^12, -a b^12, b^14}

In[158]:= solve[5]

Out[158]= {-1, a, -b^2, 0, 0, a^3 b^2 - 2 a b^4, -a^4 b^2 + 2 a^2 b^4,
  a^3 b^4 - 2 a b^6, 0, 0, -a^4 b^6 + 3 a^2 b^8 - 2 b^10, 
 a^5 b^6 - 3 a^3 b^8 + 2 a b^10, -a^4 b^8 + 3 a^2 b^10 - 2 b^12, 0, 0,
  a^3 b^12 - 2 a b^14, -a^4 b^12 + 2 a^2 b^14, 
 a^3 b^14 - 2 a b^16, 0, 0, -b^20, a b^20, -b^22}

In[159]:= solve[6]

Out[159]= {-1, a, -b^2, 0, 0, 0, 
 a^4 b^2 - 3 a^2 b^4 + b^6, -a^5 b^2 + 3 a^3 b^4 - a b^6, 
 a^4 b^4 - 3 a^2 b^6 + b^8, 0, 0, 0, -a^6 b^6 + 5 a^4 b^8 - 
  7 a^2 b^10 + 2 b^12, 
 a^7 b^6 - 5 a^5 b^8 + 7 a^3 b^10 - 2 a b^12, -a^6 b^8 + 5 a^4 b^10 - 
  7 a^2 b^12 + 2 b^14, 0, 0, 0, 
 a^6 b^12 - 5 a^4 b^14 + 7 a^2 b^16 - 2 b^18, -a^7 b^12 + 
  5 a^5 b^14 - 7 a^3 b^16 + 2 a b^18, 
 a^6 b^14 - 5 a^4 b^16 + 7 a^2 b^18 - 2 b^20, 0, 0, 0, -a^4 b^20 + 
  3 a^2 b^22 - b^24, 
 a^5 b^20 - 3 a^3 b^22 + a b^24, -a^4 b^22 + 3 a^2 b^24 - 
  b^26, 0, 0, 0, b^30, -a b^30, b^32}

In[160]:= solve[7]

Out[160]= {-1, a, -b^2, 0, 0, 0, 0, 
 a^5 b^2 - 4 a^3 b^4 + 3 a b^6, -a^6 b^2 + 4 a^4 b^4 - 3 a^2 b^6, 
 a^5 b^4 - 4 a^3 b^6 + 3 a b^8, 0, 0, 0, 0, -a^8 b^6 + 7 a^6 b^8 - 
  16 a^4 b^10 + 13 a^2 b^12 - 3 b^14, 
 a^9 b^6 - 7 a^7 b^8 + 16 a^5 b^10 - 13 a^3 b^12 + 
  3 a b^14, -a^8 b^8 + 7 a^6 b^10 - 16 a^4 b^12 + 13 a^2 b^14 - 
  3 b^16, 0, 0, 0, 0, 
 a^9 b^12 - 8 a^7 b^14 + 22 a^5 b^16 - 23 a^3 b^18 + 
  6 a b^20, -a^10 b^12 + 8 a^8 b^14 - 22 a^6 b^16 + 23 a^4 b^18 - 
  6 a^2 b^20, 
 a^9 b^14 - 8 a^7 b^16 + 22 a^5 b^18 - 23 a^3 b^20 + 
  6 a b^22, 0, 0, 0, 0, -a^8 b^20 + 7 a^6 b^22 - 16 a^4 b^24 + 
  13 a^2 b^26 - 3 b^28, 
 a^9 b^20 - 7 a^7 b^22 + 16 a^5 b^24 - 13 a^3 b^26 + 
  3 a b^28, -a^8 b^22 + 7 a^6 b^24 - 16 a^4 b^26 + 13 a^2 b^28 - 
  3 b^30, 0, 0, 0, 0, 
 a^5 b^30 - 4 a^3 b^32 + 3 a b^34, -a^6 b^30 + 4 a^4 b^32 - 
  3 a^2 b^34, a^5 b^32 - 4 a^3 b^34 + 3 a b^36, 0, 0, 0, 0, -b^42, 
 a b^42, -b^44}

In[161]:= solve[8]

Out[161]= {-1, a, -b^2, 0, 0, 0, 0, 0, 
 a^6 b^2 - 5 a^4 b^4 + 6 a^2 b^6 - b^8, -a^7 b^2 + 5 a^5 b^4 - 
  6 a^3 b^6 + a b^8, 
 a^6 b^4 - 5 a^4 b^6 + 6 a^2 b^8 - b^10, 0, 0, 0, 0, 0, -a^10 b^6 + 
  9 a^8 b^8 - 29 a^6 b^10 + 40 a^4 b^12 - 22 a^2 b^14 + 3 b^16, 
 a^11 b^6 - 9 a^9 b^8 + 29 a^7 b^10 - 40 a^5 b^12 + 22 a^3 b^14 - 
  3 a b^16, -a^10 b^8 + 9 a^8 b^10 - 29 a^6 b^12 + 40 a^4 b^14 - 
  22 a^2 b^16 + 3 b^18, 0, 0, 0, 0, 0, 
 a^12 b^12 - 11 a^10 b^14 + 46 a^8 b^16 - 90 a^6 b^18 + 81 a^4 b^20 - 
  28 a^2 b^22 + 3 b^24, -a^13 b^12 + 11 a^11 b^14 - 46 a^9 b^16 + 
  90 a^7 b^18 - 81 a^5 b^20 + 28 a^3 b^22 - 3 a b^24, 
 a^12 b^14 - 11 a^10 b^16 + 46 a^8 b^18 - 90 a^6 b^20 + 81 a^4 b^22 - 
  28 a^2 b^24 + 3 b^26, 0, 0, 0, 0, 0, -a^12 b^20 + 11 a^10 b^22 - 
  46 a^8 b^24 + 90 a^6 b^26 - 81 a^4 b^28 + 28 a^2 b^30 - 3 b^32, 
 a^13 b^20 - 11 a^11 b^22 + 46 a^9 b^24 - 90 a^7 b^26 + 81 a^5 b^28 - 
  28 a^3 b^30 + 3 a b^32, -a^12 b^22 + 11 a^10 b^24 - 46 a^8 b^26 + 
  90 a^6 b^28 - 81 a^4 b^30 + 28 a^2 b^32 - 3 b^34, 0, 0, 0, 0, 0, 
 a^10 b^30 - 9 a^8 b^32 + 29 a^6 b^34 - 40 a^4 b^36 + 22 a^2 b^38 - 
  3 b^40, -a^11 b^30 + 9 a^9 b^32 - 29 a^7 b^34 + 40 a^5 b^36 - 
  22 a^3 b^38 + 3 a b^40, 
 a^10 b^32 - 9 a^8 b^34 + 29 a^6 b^36 - 40 a^4 b^38 + 22 a^2 b^40 - 
  3 b^42, 0, 0, 0, 0, 0, -a^6 b^42 + 5 a^4 b^44 - 6 a^2 b^46 + b^48, 
 a^7 b^42 - 5 a^5 b^44 + 6 a^3 b^46 - a b^48, -a^6 b^44 + 
  5 a^4 b^46 - 6 a^2 b^48 + b^50, 0, 0, 0, 0, 0, b^56, -a b^56, b^58}

One may ask whether it is the recurrence relation of the smallest order. Clearly it is not necessarily the case. When one of $x,y,\lambda_1,\lambda_2$ is zero, the expression $f(n)=x\lambda_1^n+y\lambda_2^n$ is degenerate, and we can find a smaller recurrence relation. There can also be some cases where the relation we obtained above is not minimal, even if $x,y,\lambda_1,\lambda_2$ are nonzero. For example, when $k=4,a=4,b=1$, that is $\lambda_{1,2}=2\pm \sqrt 3$, the minimal characteristic function of $f_4(n)$ is actually $F_4(\lambda)/(\lambda+1)$. (I found this example by examining the coefficients of $\lambda_1^{sn/k}\lambda_2^{(k-s)n/k}\zeta_k^{tn}$ in the expression of $f_k(n)$, and try to find values of $\lambda_{1,2}$ to make some of them zero.)

Here is the code where I did the calculation and verification. We took $\lambda_{1,2}=2\pm \sqrt 3$, and work with the $$ F_4(\lambda)/(\lambda+1)=-\lambda ^{13}+5 \lambda ^{12}-6 \lambda ^{11}+6 \lambda ^{10}+9 \lambda ^9-69 \lambda ^8+84 \lambda ^7-84 \lambda ^6+69 \lambda ^5-9 \lambda ^4-6 \lambda ^3+6 \lambda ^2-5 \lambda +1. $$

In[91]:= (*u1=l1^(1/k), u1n=u1^n, same for u2 and u2n*)
k=4;
z:=Exp[2 Pi I/k];
getCoeff[s_,t_]:=Module[{fk},
fk=Sum[(x u1n u1^(k-r)+y u2n u2^(k-r))^r (x u1n u1^-r+y u2n u2^-r)^(k-r) Sum[(z^-r zn)^j,{j,0,k-1}]
,{r,0,k-1}];
Coefficient[Coefficient[fk,u1n^s u2n^(k-s)],zn,t]//Factor

]

In[94]:= Table[getCoeff[s,t],{s,0,k-1},{t,0,k-1}]//MatrixForm
Out[94]//MatrixForm= (4 y^4 0   0   0
((u1+u2)^2 (u1^2+u2^2)^2 x y^3)/(u1^3 u2^3) -((I (u1-u2)^2 (u1-I u2)^2 (u1+u2)^2 x y^3)/(u1^3 u2^3))    -(((u1-u2)^2 (u1^2+u2^2)^2 x y^3)/(u1^3 u2^3))  (I (u1-u2)^2 (u1+I u2)^2 (u1+u2)^2 x y^3)/(u1^3 u2^3)
((u1^2+u2^2)^2 (u1^4+4 u1^2 u2^2+u2^4) x^2 y^2)/(u1^4 u2^4) -(((u1-u2)^2 (u1+u2)^2 (u1^2+u2^2)^2 x^2 y^2)/(u1^4 u2^4))  ((u1-u2)^2 (u1+u2)^2 (u1^4-4 u1^2 u2^2+u2^4) x^2 y^2)/(u1^4 u2^4)   -(((u1-u2)^2 (u1+u2)^2 (u1^2+u2^2)^2 x^2 y^2)/(u1^4 u2^4))
((u1+u2)^2 (u1^2+u2^2)^2 x^3 y)/(u1^3 u2^3) (I (u1-u2)^2 (u1+I u2)^2 (u1+u2)^2 x^3 y)/(u1^3 u2^3)   -(((u1-u2)^2 (u1^2+u2^2)^2 x^3 y)/(u1^3 u2^3))  -((I (u1-u2)^2 (u1-I u2)^2 (u1+u2)^2 x^3 y)/(u1^3 u2^3))

)
In[95]:= polyF[k_]:=-Product[(l^k-l1^j l2^(k-j)),{j,1,k-1}] (l-l1) (l-l2);
reducedF=First@SymmetricReduction[polyF[k],{l1,l2},{4,1}]/(1+l)//Cancel;
reducedF/.l->\[Lambda]
list=CoefficientList[reducedF,l]
Out[97]= 1-5 \[Lambda]+6 \[Lambda]^2-6 \[Lambda]^3-9 \[Lambda]^4+69 \[Lambda]^5-84 \[Lambda]^6+84 \[Lambda]^7-69 \[Lambda]^8+9 \[Lambda]^9+6 \[Lambda]^10-6 \[Lambda]^11+5 \[Lambda]^12-\[Lambda]^13
Out[98]= {1,-5,6,-6,-9,69,-84,84,-69,9,6,-6,5,-1}
In[99]:= f[n_]:=x (2+Sqrt[3])^n+y (2-Sqrt[3])^n;

f[k_,n_]:=Module[{m,r},r=Mod[n,k];
m=(n-r)/k;
f[m+1]^r f[m]^(k-r)];

Do[Print[Sum[f[k,p+q] list[[p]],{p,Length[list]}]//Expand],{q,1,20}];

(* and the results are all zero*)

It's still interesting, though, to consider whether our recurrence sequence is minimal, when $x,y,a,b$ are considered algebraically independent indeterminates, i.e., the most general case.

It's also possible to give a closed form expression of $F_k(\lambda)$. We first work on the product $$ \prod_{0< j< k}(\lambda^k-\lambda_1^{j}\lambda_2^{k-j}). $$ We use the q-binomial coefficients and the Cauchy binomial theorem $$ \prod_{p=0}^{n-1}\left(1+q^p t\right)=\sum_{p=0}^n q^{p(p-1) / 2}\binom{n}{p}_q t^p, $$ and \begin{align*} \prod_{0< j< k}\left(\lambda^k-\lambda_1^{j}\lambda_2^{k-j}\right)&=\lambda^{k(k-1)}\prod_{j=1}^{k-1}\left(1-\left(\frac{\lambda_1}{\lambda_2}\right)^j\left(\frac{\lambda_2}{\lambda}\right)^k\right)\\ &=\lambda^{k(k-1)}\sum_{p=0}^{k-1}\left(\frac{\lambda_1}{\lambda_2}\right)^{p(p-1)/2}\binom{k-1}{p}_{\lambda_1/\lambda_2}\left(-\frac{\lambda_1\lambda_2^{k-1}}{\lambda^k}\right)^p. \end{align*} where we take $n=k-1,t=-\frac{\lambda_1\lambda_2^{k-1}}{\lambda_k},q=\lambda_1/\lambda_2$.

So the conclusion is

$$ F_k(\lambda)=(\lambda-\lambda_1)(\lambda-\lambda_2)\lambda^{k(k-1)}\sum_{p=0}^{k-1}\left(\frac{\lambda_1}{\lambda_2}\right)^{p(p-1)/2}\binom{k-1}{p}_{\lambda_1/\lambda_2}\left(-\frac{\lambda_1\lambda_2^{k-1}}{\lambda^k}\right)^p. $$

Again, we verify this is correct using Mathematica for small $k$.

In[227]:= 
verify[k_] := 
  Product[(l^k - l1^j l2^(k - j)), {j, 1, k - 1}] - 
     l^((k - 1) k) Sum[(l1/l2)^(p (p - 1)/2) QBinomial[k - 1, p, 
         l1/l2] (-l1 l2^(k - 1)/l^k)^p, {p, 0, k - 1}] // 
    FunctionExpand // Expand;

In[233]:= verify[2]

Out[233]= 0

In[228]:= verify[3]

Out[228]= 0

In[230]:= verify[4]

Out[230]= 0

In[231]:= verify[5]

Out[231]= 0

In[232]:= verify[6]

Out[232]= 0
```