We are interested which integer sequences are efficiently computable possibly over finite rings.
Define the integer sequence $a(n)=(b_1 n +b_2)a(n-1)+(b_3 n + b_4)a(n-2)$ with initial terms $a(0),a(1)$.
Denote the near neighbors of $a(n)$ to be $a(n+1),a(n+2)...,a(n+k)$. I am interested in doubling or addition formulas for sequences related to $a(n)$.
Doubling is given near neighbors of $a(n)$, compute $a(2n)$.
Addition formula is defined as given near neighbors of $a(n)$ and near neighbors $a(u)$, compute $a(n+u)$.
If both $b_1,b_3$ are zero, $a(n)$ is linear recurrence with constant coefficients and doubling formulas exist.
If at least one of $b_1,b_3$ is non-zero, then $a(n)$ grows super factorial, very roughly $n^n$, so rational doubling or addition formulas don't exist because of growth arguments.
Define the sequence $b(n)=a(n+1)/a(n)$.
If $a(n)=n a(n-1)=n!$ then $b(n)=n+1$ has simple doubling formula because of the easy closed form.
Q1 Are there other choices of $b_i$ for which doubling or addition formulas exist for $b(n)$? We are interested in complexity $O((\log{n})^m)$, possibly working over finite fields or rings.
