Question

Let $F_{i}$ be the fibonacci or a multinacci sequence. The number of representations of $N$ in the form $ N=\sum_{i=0}^{k}s_{i}F_{i}, s_{i}\in ${0,1} is known.

My question is what is known about sequence-based numeration systems given by other linear recurrences.

To make the question precise, i am interested in the recurrence $ G_{i+4}=G_{i+3}+G_{i+2}+G_{i+1}-G_{i}$ with $G_{0}=1$, $G_{1}=2$, $G_{2}=4$, $G(3)=8$.

What is known about $ \sharp_{G} N:=${$(s_{0},\dots,s_{k})\in${0,1}$^{k+1}|N=\sum_{i=0}^{k}s_{i}G_{i}$}?

Answer 1

Some results on the quantity in question can be found in

J. M. Dumont, N. Sidorov and A. Thomas, Number of representations related to a linear recurrent basis, Acta Arithmetica 88 (1999), 371-394.

We are mainly interested in the summatory function but there are also some upper bounds for the quantity itself. Our main assumption is that the corresponding root (of $x^4=x^3+x^2+x-1$ in your case) is a Perron number (in your example it's even Salem, so our results apply).