On the average density of non-zero digits of NAFs of fixed length

Question

An NAF is a non-adjacent form of a positive integer $k$.

One of the five properties of NAFs is "The average density of non-zero digits among all NAFs of length $l$ is approximately $1/3$."

How to prove it?

Thanks.

Answer 1

The number of NAFs of length $n$ and $k$ nonzero digits is equal to $2^{k-1}\binom{n-k}{k}$. Therefore the total number of NAFs of length $n$ is $$A_n=\sum_{k\geq 0} 2^{k-1}\binom{n-k}{k}$$ and the total number of nonzero digits that appear in the set of all NAFs of length $n$ is $$B_n=\sum_{k\geq 0} k\cdot2^{k-1}\binom{n-k}{k}.$$ Now, the density you seek is given by $\frac{B_n}{nA_n}$ and perhaps there is a slick way to get the approximation quickly, but a boring way is to proceed by determining this value exactly.

You can routinely check the recurrence relations satisfied by both $A_n$ and $B_n$, or their generating functions. We have $$\sum_{n\geq 0}A_{n+1}x^{n}=\frac{1}{1-x-2x^2}$$ $$\sum_{n\geq 0} B_{n+1}x^n=\frac{1-x}{(1-x-2x^2)^2}$$ from which you can deduce explicit formulas for each sequence. You'll find $$A_n=\frac{2^n-(-1)^n}{3} \, , \, B_n=\frac{n2^{n}}{9}+O(2^n)$$ which means that the average density of nonzero digits is $B_n/nA_n=\frac{1}{3}+O(1/n)$.