A combinatorial interpretation of double base number system and some consequences (Q935619)

A non-standard number system, called double base number system (DBNS) [\textit{V. S. Dimitrov}, \textit{G. A. Jullien} and \textit{W. C. Miller}, ``Theory and applications of the double-base number system'', IEEE Trans. Comput. 48, 1098--1106 (1999)], has recently found several applications in Signal Processing and Cryptography. The authors use DBNS graphs to prove the following recurrence relation for the number of DBNS representations \(P_s(n)\) of any positive integer \(n\) using the bases 2 and \(s\): \(P_s(1)=1\), and, for \(n>1\), \[ P_s(n) = \begin{cases} P_s(n-1) + P_s(n/s)\quad&\text{if }s \mid n,\\ P_s(n-1)&\text{otherwise.}\end{cases} \] They also generalize this result to more than two bases.