On the representation of C-recursive integer sequences by arithmetic terms (Q6925531)

This paper deals with linear recurrence (or C-recursive) integer sequences. The main result is a constructive method to produce a closed form expression of the \(n\)-th term by using only basic arithmetic operations on integers. The method is based on the generating function \(\mathrm{GF}\) of the sequence from which it is possible to extract directly a given coefficient when applied to a suitably chosen rational number. The general expression is of the form \N\[\N\left( \left\lfloor b^{n^2} \, \mathrm{GF}(b^{-n}) \right\rfloor \bmod b^n \right) - c^{n+1}\N\]\Nwhere \(b \geq 2\) and \(c \geq 0\) are fixed integers. In the case of a nonnegative sequence, it can be simplified by setting \(c=0\). According to the authors, previously known methods typically give much larger expressions.\N\NThey provide many examples which are mostly Lucas sequences of positive or negative discriminant. In the particular case of the Fibonacci numbers \(F_n\), they find that \N\[\NF_n = \left\lfloor \frac{2^{n^2+n}}{2^{2n}-2^{n}-1} \right\rfloor \bmod 2^n\N\]\Nas soon as \(n \geq 2\). This formula does not involve any irrational numbers like \(\sqrt{5}\) but implies dealing with large integers like \(2^{n^2}\), which may also induce a practical limitation to its use.