Can the Fibonacci sum $\sum_{i=0}^N x^i F_{a+ib}$, for integers $x$, $a$, $b$, be determined by a direct formula or generating function?

Question

Suppose we have a variable $x$ such that $x\in\mathbb{N}$. Let

$$S=\sum_{i=0}^N F_{a+i.b}. x^i$$

where $F_i$ is the $i$-th Fibonacci number, $a$ and $b$ are constants having range between $0\leq a,b\leq10^{9}$, and $N$ can be a big value up to $10^{18}$

Here's an example let's suppose $a=0,b=2,x=1,N=4$ then $$S=F_0+F_2+F_4+F_6+F_8=33$$

Can $S$ be solved using a direct formula or maybe a generating function? If yes, how?

Answer 1

The $n$-th Fibonacci number is $$F_n=\frac{1}{\sqrt5}(\phi^n-\psi^n),$$ where $\phi=\frac{1}{2}(1+\sqrt5)$ and $\psi=\frac12(1-\sqrt5)$. Thus $$\begin{align} S&=\sum_{k=0}^NF_{a+bk}x^k\\ &=\sum_{k=0}^N\frac{1}{\sqrt5}(\phi^{a+bk}-\psi^{a+bk})x^k\\ &=\frac{\phi^a}{\sqrt5}\sum_{k=0}^N(\phi^bx)^k-\frac{\psi^a}{\sqrt5}\sum_{k=0}^N(\psi^bx)^k\\ &=\frac{\phi^a}{\sqrt5}\cdot\frac{(\phi^bx)^N-1}{\phi^bx-1}-\frac{\psi^a}{\sqrt5}\cdot\frac{(\psi^bx)^N-1}{\psi^bx-1}. \end{align}$$ This is of course making the assumption that $x\ne \phi^{-b},\psi^{-b}$.