Take the 2-minute tour ×

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}$}?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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).

share|improve this answer
Many thanks for the reference. Best 9i –  Jörg Neunhäuserer Feb 16 '13 at 15:39
No problem. Hope it'll help. –  Nikita Sidorov Feb 16 '13 at 22:41

Your Answer


