In work of mine recently, I have come to investigate generalised recurrence relations. The generalisation I have in mind is where, instead of natural numbers or integers, the recurrence is over some other ring - my particular case being the cyclotomic integers.

One particular case of interest for me is a generalisation of the Fibonacci numbers. The classic recurrence may be written in the form:

$$f_{j} = f_{j+1} + (-1)f_{j-1}$$

where j is an integer. The specific series of Fibonacci includes the initial data the $f_0=0$ and $f_1=1$.

I write it this way because I am interested in the generalisation given by:

$$f_{n,\alpha} = \sum_{k=0}^{n-1} \omega_{n}^{k} f_{n,\alpha+\omega_{n}^{k}}$$

where

$ω_n=e^{2πi/n}$ (an nth root of unity).

The $\alpha$ here can now be any order-n cyclotomic integer. The n=2 case gives the classic Fibonacci.

As a way to solve this, I tried some standard generatingfunctionology. Instead of power series, though, I use the extended group ring over the cyclotomics (so I expand with terms that include x^(ω_n^k ) and terms generated from them). I need to first define the boundary conditions for this, which is more complex than the n=2 case but I can keep the derivation very general here. In other words, I decide to look at generating function

$$G_{n}(x) = \sum_{\alpha \in C_{n}} f_{n, \alpha} x^{\alpha}$$

over the cyclotomic integers $C_n$.

This gives a result that I seem to be able to extract information from:

$$G_{n}(x) = \frac{H_{n}\[B(f_{n}); x\] - \sum_{j=0}^{n-1} \omega_{n}^{j} x^{-\omega_{n}^{j}} H_{n}\[ \overline{I(f_{n}) + \omega_{n}^{j}}; x\] }{1 - \sum_{j=0}^{n-1} \omega_{n}^{j} x^{\omega_{n}^{j}}}$$

Where I have defined the sum over set S

$$H_{n}\[S;x\] = \sum_{\alpha \in S} f_{n,\alpha} x^{\alpha}$$

such that the set $B(f_{n})$ is the set of boundary value places defined for the problem, $I(f_{n})$ is the set of interior places determined by the boundary set, and the overbar indicates complement with respect to the cyclotomic integers. In other words, I can find how the generating function will look using formal manipulations on the group ring that accounts for the different initial value choices that might be given for the problem.

But here is my problem: I don’t know if those formal manipulations are completely valid. When looking at these extended group rings, there are equivalent expansions that make it much more risky to blindly do formal manipulations than with traditional power series. An easy example is the formal extended Laurent series

$$...+x^{-4}+x^{-3}+x^{-2}+x^{-1}+1+x+x^2+x^3+x^4+...$$

If we try to expand this as two geometric series, we might expand this into the generating function

$$\frac{1}{1-x} + \frac{x^{-1}}{1 - x^{-1}}$$

But if you do this and simplify, you get 0! It's clear that such a function would formally obey xf=f if we ignore convergence issues. Obviously 0 isn’t a good generating function for the infinite vector of 1s! And the same for an infinite vector of any constant. Such problems with simple manipulations don’t arise in the power series case. So one big caveat is that such generalised structures have formally distinct representations with the same behavior, and manipulation may switch between them.

Interestingly, the case for n=2 with standard boundary at 0 and 1 gives:

$$G_{2}(x) = \frac{-1}{1+x-x^{-1}}$$

from which I can extract the standard generating functions on either side of the boundary by multiplying by $\frac{x}{x}$ or $\frac{x^{-1}}{x^{-1}}$. Similarly can I extract meaningful values from my solution along subset regions for higher n.

Here are two pictures (one, two) of the formal manipulations I used to obtain the result above (rather than typing the whole thing out). I don’t have any familiarity with actual references on what formal manipulations on extended group rings are considered “valid” for generating functions (i.e. which ones will maintain the generated values) and where caution is needed. I understand that some of these concerns are why group rings are typically defined with finite support and why Laurent series are typically only finitely extended along one of the rays, but there is good combinatorics done with bilateral series and the generalisation does seem to give good extractable information.

Any help with references that explore these areas would be greatly appreciated! If you know of rules or explicit manipulations that fail or are guaranteed to work, that would help me start to get a handle on this. Also, any other methods for solving such generalised recurrence relations would be appreciated. I have looked at operator theory and directional differences, but they have a much deeper set of relations and I seem to get lost trying to apply them constructively here. But any algebraic techniques would really help out.

[As a note: the above recurrence may seem arbitrary and unmotivated. However, it is directly related to work I have done on generalised Chebyshev “polynomials”, which arise from the natural generalisation of trigonometry. These generalised Fibonacci actually “occur in the wild”, so to speak.]