Counting Non-Standard Binary Representations

Katie Anders^{1} Department of Mathematics University of Texas at Tyler 3900 University Blvd. Tyler, TX 75799 USA

                      kanders@uttyler.edu

Abstract Let be a finite subset of ℕ including 0 and let f_{}n be the number of ways to write n _{i 0}^{}ϵ_{i}2^{i}, where ϵ_{i} . We consider asymptotics of the summatory function s_{}r, m of f_{}n from m2^{r} to m2^{r 1} 1, and show that s_{}r, m c , m ^{r} for some nonzero c , m ℚ.

1 Introduction

Let f_{}n denote the number of ways to write n _{i 0}^{}ϵ_{i}2^{i}, where ϵ_{i} belongs to the set

0 a_{0}, a_{1}, …, a_{z} ,

with a_{i} ℕ and a_{i} a_{i 1} for all 0 i z 1. For more on this topic, see the author’s previous work [1]. We parameterize in terms of its s even elements and z 1 s t odd elements as follows:

0 2b_{1}, 2b_{2}, …, 2b_{s}, 2c_{1} 1, …, 2c_{t} 1 .

1The author acknowledges support from National Science Foundation grant DMS 08-38434, “EMSW21-MCTP: Research Experience for Graduate Students”.

If n is even, then ϵ_{0} 0, 2b_{2}, 2b_{3}, …, or 2b_{s} and

f_{}n f_{}n 2 f_{}n 2b_{2} 2 f_{}n 2b_{3} 2 f_{}n 2b_{s} 2 .

Writing n 2ℓ, we have

f_{}2ℓ f_{}ℓ f_{}ℓ b_{2} f_{}ℓ b_{3} f_{}ℓ b_{s} ,

so for any even n, f_{}n satisfies a recurrence relation of order b_{s}.

Similarly, if n 2ℓ 1 is odd, then ϵ_{0} 2c_{1} 1, 2c_{2} 1, …, or 2c_{t} 1, and

f_{}2ℓ 1 f_{}ℓ c_{1} f_{}ℓ c_{2} f_{}ℓ c_{t} ,

so for any odd n, f_{}n satisfies a recurrence relation of order c_{t}. Dennison, Lansing, Reznick, and the author [3] gave this argument for f_{,b} n , the b-ary representation of n with coefficients from , using residue classes mod b.

Example 1. Let  0, 1, 3, 4 . We can write  2 0 , 2 0 1, 2 1 1, 2 2 . Then
f_{}2ℓ f_{}ℓ f_{}ℓ 2 and f_{}2ℓ 1 f_{}ℓ f_{}ℓ 1 .  (1)

In general, let

ω_{k} m ; ; ; ; \begin{matrix}f_{}2^{k}m \\ f_{}2^{k}m 1 \\ \\ f_{}2^{k}m a_{z} \end{matrix} ; ; ; ; .

We shall consider the fixed a_{z} 1 a_{z} 1 matrix M_{}such that for any k 0,

ω_{k 1} M_{}ω_{k}.

Example 2. Returning to the set 0, 1, 3, 4 of Example 1 and using the equations in (1), we have

ω_{k 1} m  ;  ;  ;  ;  ;  ;  ; \begin{matrix}f_{}2^{k 1}m \\ f_{}2^{k 1}m 1 \\ f_{}2^{k 1}m 2 \\ f_{}2^{k 1}m 3 \\ f_{}2^{k 1}m 4 \end{matrix}  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ; \begin{matrix}f_{}2^{k}m f_{}2^{k}m 2 \\ f_{}2^{k}m 1 f_{}2^{k}m 2 \\ f_{}2^{k}m 1 f_{}2^{k}m 3 \\ f_{}2^{k}m 2 f_{}2^{k}m 3 \\ f_{}2^{k}m 2 f_{}2^{k}m 4 \end{matrix}  ;  ;  ;  ;  ;  ;  ; (2)

; ; ; ; ; ; ; 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 ; ; ; ; ; ; ; ; ; ; ; ; ; ; \begin{matrix}f_{}2^{k}m \\ f_{}2^{k}m 1 \\ f_{}2^{k}m 2 \\ f_{}2^{k}m 3 \\ f_{}2^{k}m 4 \end{matrix} ; ; ; ; ; ; ;

If M_{}is the matrix in (2), then ω_{k 1} m M_{}ω_{k} m .

We now review some basic concepts of sequences from Section 8.1 of Lidl and Niederreiter [5] and include a matrix view of recurrence relations, following Reznick [6].

Consider a sequence b n such that

b n c_{k 1}b n 1 c_{k 2}b n 2  c_{0}b n k 0  (3)

for all n k and c_{i} ℕ. By shifting the sequence, we see that

b n k c_{k 1}b n k 1 c_{k 2}b n k 2  c_{0}b n k k 0  (4)

for n 0. Then (3) is a homogeneous k-th order linear recurrence relation, and b n is a homogeneous k-th order linear recurrence sequence. For any sequence b n satisfying (3) we define the characteristic polynomial

f x x^{k} c_{k 1}x^{k 1} c_{k 2}x^{k 2}  c_{0}.  (5)

We can also consider a recurrence relation from the point of view of a matrix system, considering k sequences indexed as b_{i} n for 1 i k which satisfy

b_{i} n 1 _{j 1}^{k} m_{ij}b_{j} n

for n 0 and 1 i k. Then

; ; \begin{matrix}b_{1} n 1 \\ \\ b_{k} n 1 \end{matrix} ; ; ; ; \begin{matrix}m_{11} & & m_{1k} \\ & & \\ m_{k1} & & m_{kk} \end{matrix} ; ; ; ; \begin{matrix}b_{1} n \\ \\ b_{k} n \end{matrix} ; ;

for n 0. To simplify the notation, if M m_{ij} and

B n ; ; \begin{matrix}b_{1} n \\ \\ b_{k} n \end{matrix} ; ; ,

then B n 1 MB n for n 0. Thus B n M^{n}B 0 for n 0, where

B 0 ; ; \begin{matrix}b_{1} 0 \\ \\ b_{k} 0 \end{matrix} ; ;

is the vector of initial conditions.

As an additional connection between these two views of linear recurrence sequences, note that for a sequence satisfying (3),

; ; ; ; ; ; ; \begin{matrix}b n 1 \\ b n 2 \\ \\ b n k 1 \\ b n k \end{matrix} ; ; ; ; ; ; ; ; ; ; ; ; ; ; \begin{matrix}0 & 1 & & 0 & 0 \\ 0 & 0 & & 0 & 0 \\ & & & & \\ 0 & 0 & & 0 & 1 \\ c_{0} & c_{1} & & c_{k 2} & c_{k 1} \end{matrix} ; ; ; ; ; ; ; ; ; ; ; ; ; ; \begin{matrix}b n \\ b n 1 \\ \\ b n k 2 \\ b n k 1 \end{matrix} ; ; ; ; ; ; ; ,

where this matrix, the companion matrix to g, has characteristic polynomial 1 ^{k}g. In this matrix point of view, the characteristic polynomial of M is

g λ det M λI_{k} .

By the Cayley-Hamilton Theorem, g M 0, the k k zero matrix.

If g x is the characteristic polynomial in (5), then

0 g M M^{k} c_{k 1}M^{k 1} c_{k 2}M^{k 2} c_{0}I_{k}.

Hence for any n 0,

0 M^{n k} c_{k 1}M^{n k 1} c_{k 2}M^{n k 2} c_{0}M^{n}

and thus

0 M^{n k} c_{k 1}M^{n k 1} c_{k 2}M^{n k 2}  c_{0}M^{n} B 0
B n k c_{k 1}B n k 1 c_{k 2}B n k 2 c_{0}B n .

Thus each sequence b_{j} n satisfies the original linear recurrence (4).

2 Main result

We will use the ideas of Section 1 to examine the asymptotic behavior of the summatory

function _{n m2^{r}}^{m2^{r 1} 1} f_{}n , but we must first establish a lemma.

Lemma 3 ([4, 5.6.5 & 5.6.9]). Let M m_{ij} be an n n matrix with characteristic polynomial g λ and eigenvalues λ_{1}, λ_{2}, …, λ_{y}. Then

max_{1 i y} λ_{i} max_{1 i n}_{j 1}^{n} m_{ij} .

Theorem 4. Let , f_{}n , M_{}, and ω_{k} m be as above, with the additional assumption that there exists some odd a_{i} . Define

s_{}r, m _{n m2^{r}}^{m2^{r 1} 1} f_{}n .

Let denote the number of elements in the set . Then for a fixed value of m,

lim_{r} \frac{s_{}r, m}{^{r}} c , m ,

for some nonzero constant c , m ℚ, so s_{}r, m c , m ^{r}.

Proof. Let g λ det M_{}λI be the characteristic polynomial of M_{}with eigenvalues λ_{1}, λ_{2}, …, λ_{y}, where each λ_{i} has multiplicity e_{i}. We can write

g λ _{k 0}^{a_{z} 1} α_{k}λ^{k}.

By Cayley-Hamilton, we know that g M_{}0. Thus we have

0 g M_{}_{k 0}^{a_{z} 1} α_{k}M_{}^{k}

and hence, for all r,

0 _{k 0}^{a_{z} 1} α_{k}M_{}^{k} ω_{r} m _{k 0}^{a_{z} 1} α_{k}ω_{r k} m .

Since

ω_{r k} m ; ; ; ; \begin{matrix}f_{}2^{r k}m \\ f_{}2^{r k}m 1 \\ \\ f_{}2^{r k}m a_{z} \end{matrix} ; ; ; ; ,

we have

_{k 0}^{a_{z} 1} α_{k}f 2^{r k}m j 0  (6)

for all 0 j a_{z}.

Let I_{r} 2^{r}, 2^{r} 1, 2^{r} 2, …, 2^{r 1} 1 . Then I_{r} 2I_{r 1} 2I_{r 1} 1 . Thus

s_{}r, m _{n m2^{r}}^{m2^{r 1} 1} f_{}n

_{n m2^{r 1}}^{m2^{r} 1} f_{}2n f_{}2n 1

_{n m2^{r 1}}^{m2^{r} 1} f_{}n f_{}n b_{2}  f_{}n b_{s} f_{}n c_{1}  f_{}n c_{t}  .

Since

_{n m2^{r 1}}^{m2^{r} 1} f_{}n k _{n m2^{r 1}}^{m2^{r} 1} f_{}n _{j 1}^{k} f_{}m2^{r 1} j f_{}m2^{r} j ,

we deduce that

s_{}r, m  _{n m2^{r 1}}^{m2^{r} 1} f_{}n h r, m
s_{}r 1, m h r, m ,

where

h r, m _{i 2}^{s} _{j 1}^{b_{i}} f_{}m2^{r 1} j f_{}m2^{r} j _{i 1}^{t} _{j 1}^{c_{i}} f_{}m2^{r 1} j f_{}m2^{r} j

and

_{k 0}^{a_{z} 1} α_{k}h r k, m 0

by Equation (6).

Thus we have an inhomogeneous recurrence relation for s_{}r, m and will first consider the corresponding homogeneous recurrence relation

s_{}r, m s_{}r 1, m ,

which has solution s_{}r, m c ^{r}. Then the solution to our inhomogeneous recurrence relation is of the form

s_{}r, m c ^{r} _{i 1}^{y} p_{i} λ_{i}, r ,

where

p_{i} λ_{i}, r _{j 1}^{e_{i}} c_{ij}r^{j 1}λ_{i}^{r}.

By Lemma 3, λ_{i} is bounded above by the maximum row sum of M_{}, which is at most 1 since all elements of M_{}are either 0 or 1 and by assumption not all elements have the same parity. Hence the c ^{r} term dominates s_{}r, m as r , so

lim_{r} \frac{s_{}r, m}{^{r}} c.

Observe that

_{k 0}^{a_{z} 1} α_{k} _{i 1}^{y} p_{i} λ_{i}, r k 0.

Thus we can compute _{k 0}^{a_{z} 1} α_{k}s_{}r k, m , and for sufficiently large r,

_{k 0}^{a_{z} 1} α_{k}s_{}r k, m c _{k 0}^{a_{z} 1} α_{k}  ^{r k} 0 c ^{r} g  .

Then we can solve for c to see that

c c , m \frac{_{k 0}^{a_{z} 1} α_{k}s_{}r k, m}{^{r} g} .  (7)

It remains to be shown that c A, m 0, and we thank the referee for raising this point. For a particular value of n, all ^{n} sums of the form

_{i 0}^{n 1} ϵ_{i}2^{i}, ϵ_{i} 0 a_{0} a_{1} a_{z}

have the value of the sum less than or equal to a_{z} 2^{n} 1 . Thus

f_{}0 f_{}1 f_{}a_{z} 2^{n} 1 ^{n}. (8)

Fix m. There exists ℓ ℕ such that m2^{ℓ} a_{z}. Then

f_{}0 f_{}1 f_{}a_{z} 2^{n} 1 f_{}0 f_{}1 f_{}m2^{n ℓ} 1 (9)
s_{}0, m s_{}1, m s_{}n ℓ 1, m .

Combining (8) and (9), we have

n s_{}0, m s_{}1, m s_{}n ℓ 1, m .

We know from above that s_{}r, m c , m o 1 ^{r}. Thus

n c , m o 1 ^{0} ^{1} ^{2} ^{n ℓ 1}

c , m o 1 \frac{^{n ℓ}}{1}.

Dividing both sides by ^{n}, we see that

1 c , m o 1 \frac{^{ℓ}}{1}.

Hence c , m 0 and s_{}r, m c , m ^{r}.

3 Examples

Example 5. Let 0, 1, 8 . Then

f_{}2ℓ f_{}ℓ f_{}ℓ 4  (10)

and

f_{}2ℓ 1 f_{}ℓ ,  (11)

so

; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; \begin{matrix}f_{}2^{k 1}m \\ f_{}2^{k 1}m 1 \\ f_{}2^{k 1}m 2 \\ f_{}2^{k 1}m 3 \\ f_{}2^{k 1}m 4 \\ f_{}2^{k 1}m 5 \\ f_{}2^{k 1}m 6 \\ f_{}2^{k 1}m 7 \\ f_{}2^{k 1}m 8 \end{matrix} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; \begin{matrix}f_{}2^{k}m \\ f_{}2^{k}m 1 \\ f_{}2^{k}m 2 \\ f_{}2^{k}m 3 \\ f_{}2^{k}m 4 \\ f_{}2^{k}m 5 \\ f_{}2^{k}m 6 \\ f_{}2^{k}m 7 \\ f_{}2^{k}m 8 \end{matrix} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; .

If M_{}is the matrix above, then ω_{k 1} m M_{}ω_{k} m . The characteristic polynomial of M_{} is

g x 1 3x 3x^{2} 3x^{3} 6x^{4} 6x^{5} 3x^{6} 3x^{7} 3x^{8} x^{9}.  (12)

We then compute

s_{}3, 1 3s_{}4, 1 3s_{}5, 1 3s_{}6, 1 6s_{}7, 1 6s_{}8, 1

3s_{}9, 1 3s_{}10, 1 3s_{}11, 1 s_{}12, 1 59184

Using the formula from Theorem 4, we see that

c , 1 \frac{59184}{g 3 27} \frac{59184}{5408 27} \frac{137}{338}.

Example 6. Let 0, 1, 3 . Then

f_{}2ℓ f_{}ℓ  (13)

and

f_{}2ℓ 1 f_{}ℓ f_{}ℓ 1 ,  (14)

so

; ; ; ; \begin{matrix}f_{}2^{k 1}m \\ f_{}2^{k 1}m 1 \\ f_{}2^{k 1}m 2 \\ f_{}2^{k 1}m 3 \end{matrix} ; ; ; ; ; ; ; ; 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 ; ; ; ; ; ; ; ; \begin{matrix}f_{}2^{k}m \\ f_{}2^{k}m 1 \\ f_{}2^{k}m 2 \\ f_{}2^{k}m 3 \end{matrix} ; ; ; ; .

Hence M_{} ; ; ; ; 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 ; ; ; ; satisfies ω_{k 1} m M_{}ω_{k} m . The characteristic polynomial of

M_{}is

g x x 1 ^{2} x^{2} x 1 .  (15)

Let F_{k} denote the k-th Fibonacci number. Then

f_{}2^{k} 1 F_{k 1}  (16)

for all k 0. This can be shown by using induction and Equations (13) and (14).

Considering the summatory function with m 1 and using Equations (13),(14), and (16), we see that

s_{}r, 1 _{n 2^{r}}^{2^{r 1} 1} f_{}n

_{n 2^{r 1}}^{2^{r} 1} f_{}2n f_{}2n 1

_{n 2^{r 1}}^{2^{r} 1} f_{}n f_{}n f_{}n 1

2s_{}r 1, 1 _{n 2^{r 1}}^{2^{r} 1} f_{}n 1

2s_{}r 1, 1 _{n 2^{r 1}}^{2^{r} 1} f_{}n f_{}2^{r 1} 1 f_{}2^{r} 1

3s_{}r 1, 1 f_{}2^{r 1} 1 f_{}2^{r} 1

3s_{}r 1, 1 F_{r} F_{r 1} 3s_{}r 1, 1 F_{r 1}.

This is an inhomogeneous recurrence relation for s_{}r, 1 . We first consider the corresponding homogeneous recurrence relation s_{}r, 1 3s_{}r 1, 1 , which has solution

s_{}r, 1 d_{1}3^{r},

for some d_{1} in ℚ. Recall that the characteristic polynomial g x of M_{}has roots 1, ϕ, and ϕ̄, where the first has multiplicity 2 and the others have multiplicity 1. Hence the solution to the inhomogeneous recurrence relation is

s_{}r, 1 d_{1}3^{r} d_{2}ϕ^{r} d_{3}ϕ̄^{r} d_{4} 1 ^{r} d_{5}r 1 ^{r},  (17)

where d_{2}, d_{3}, d_{4}, d_{5} ℚ. Observe that the d_{1}3^{r} summand will dominate as r , so

lim_{r} \frac{s_{}r, 1}{3^{r}} d_{1}

and s_{}r, 1 d_{1}3^{r}.

Using Equations (15) and (17), we can compute d_{1} as

s_{}r 2, 1 s_{}r 1, 1 s_{}r, 1 d_{1}3^{r} 3^{2} 3 1 d_{2}ϕ^{r} ϕ^{2} ϕ 1

d_{3}ϕ̄^{r} ϕ̄^{2} ϕ̄ 1 d_{4} 1^{2} 1 1 d_{5} r 2 r 1 r d_{1}3^{r} 5 d_{4} d_{5} r 1 .

Plugging in r 2, r 1, and r 0 and computing sums, we see that d_{1} 4 5. Hence

lim_{r} \frac{s_{}r, 1}{3^{r}} \frac{4}{5}

and s_{}r, 1 \frac{4}{5} 3^{r}.

Example 7. Let ˜ 0, 2, 3 . Then

f ˜ 2ℓ f ˜ ℓ f ˜ ℓ 1  (18)

and

f ˜ 2ℓ 1 f ˜ ℓ 1 ,  (19)

so

; ; ; ; \begin{matrix}f ˜ 2^{k 1}m \\ f ˜ 2^{k 1}m 1 \\ f ˜ 2^{k 1}m 2 \\ f ˜ 2^{k 1}m 3 \end{matrix} ; ; ; ; ; ; ; ; 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 ; ; ; ; ; ; ; ; \begin{matrix}f ˜ 2^{k}m \\ f ˜ 2^{k}m 1 \\ f ˜ 2^{k}m 2 \\ f ˜ 2^{k}m 3 \end{matrix} ; ; ; ; .

Hence M ˜ ; ; ; ; 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 ; ; ; ; satisfies ω_{k 1} m M ˜ ω_{k} m . The characteristic polynomial of

M ˜ is

g x x 1 ^{2} x^{2} x 1 .  (20)

Let F_{k} denote the k-th Fibonacci number. Then

f ˜ 2^{k} 1 F_{k 1}  (21)

for all k 1. This can be shown by using induction and Equations (18) and (19) to prove that f ˜ 2^{k} 2 F_{k} for all k 2 and observing that Equation (19) gives f ˜ 2^{k} 1 f ˜ 2^{k 1} 2 .

Considering the summatory function with m 1 and using Equations (18),(19), and (21) and manipulations similar to those in Example 6, we see that

s ˜ r, 1 3s ˜ r 1, 1 2F_{r 3}.

Again, the corresponding homogeneous recurrence relation has solution

s ˜ r, 1 d_{1}3^{r},

for some d_{1} in ℚ, and we can use Equation (20) to see that the solution to the inhomogeneous recurrence relation is

s ˜ r, 1 d_{1}3^{r} d_{2}ϕ^{r} d_{3}ϕ̄^{r} d_{4} 1 ^{r} d_{5}r 1 ^{r},  (22)

where d_{2}, d_{3}, d_{4}, d_{5} ℚ. Observe that the d_{1}3^{r} summand will dominate as r , so

lim_{r} \frac{s ˜ r, 1}{3^{r}} d_{1}

and s ˜ r, 1 d_{1}3^{r}.

Using Equations (20) and (22), we can compute d_{1} as

s ˜ r 2, 1 s ˜ r 1, 1 s ˜ r, 1 d_{1}3^{r} 5 d_{4} d_{5} r 1 .

Plugging in r 2, r 1, and r 0 and computing sums, we see that d_{1} 2 5. Hence

lim_{r} \frac{s ˜ r, 1}{3^{r}} \frac{2}{5}

and s ˜ r, 1 \frac{2}{5} 3^{r}.

In Example 6, we had 0, 1, 3 , and in Example 7, we had ˜ 0, 2, 3 3 3, 3 1, 3 0 . We found c , 1 in Example 6 and c ˜ , 1 in Example 7 and can observe that they have the same denominator.

Given a set 0, a_{1}, …, a_{z} , let ˜ be

˜ 0, a_{z} a_{z 1}, …, a_{z} a_{1}, a_{z} .

The following chart displays the value c , 1 for various sets and their corresponding sets ˜ , where s_{}r, 1 c , 1 ^{r}. Note that in all cases the denominator of c , 1 is the same as that of c ˜ , 1 . The following theorem will show that this holds for all .

\begin{matrix} & c , 1 & N c , 1 & & ˜ c ˜ , 1 & N c ˜ , 1 \\ 0, 1, 2, 4 & \frac{7}{11} & 0.636 & 0, 2, 3, 4 & \frac{3}{11} & 0.273 \\ 0, 1, 3, 4 & \frac{1}{2} & 0.500 & 0, 1, 3, 4 & \frac{1}{2} & 0.500 \\ 0, 2, 3, 6 & \frac{33}{149} & 0.221 & 0, 3, 4, 6 & \frac{21}{149} & 0.141 \\ 0, 1, 6, 9 & \frac{6345}{28670} & 0.221 & 0, 3, 8, 9 & \frac{2007}{28670} & 0.070 \\ 0, 1, 7, 9 & \frac{2069}{10235} & 0.202 & 0, 2, 8, 9 & \frac{1023}{10235} & 0.100 \\ 0, 4, 5, 6, 9 & \frac{4044}{83753} & 0.048 & 0, 3, 4, 5, 9 & \frac{6716}{83753} & 0.080 \end{matrix}

Table 1: c , 1 for various sets and ˜ Theorem 8. Let , f_{}n , M_{}m_{α,β} , and ˜ be as above, with 0 α, β a_{z}. Let M ˜ mα,β^{}be the a_{z} 1 a_{z} 1 matrix such that

; ; ; ; \begin{matrix}f ˜ 2n \\ f ˜ 2n 1 \\ \\ f ˜ 2n a_{z} \end{matrix} ; ; ; ; M ˜ ; ; ; ; \begin{matrix}f ˜ n \\ f ˜ n 1 \\ \\ f ˜ n a_{z} \end{matrix} ; ; ; ; .

Then m_{α,β} ma_{z} α,a_{z} β^{}.

Proof. Recall that we can write

0, 2b_{2}, …, 2b_{s}, 2c_{1} 1, …, 2c_{t} 1 ,

so that

f_{}2n 2j f_{}n j f_{}n j b_{2} f_{}n j b_{s}

and

f_{}2n 2j 1 f_{}n j c_{1} 1 f_{}n j c_{t} 1

for j sufficiently large.

Then m_{α,β} 1 if and only if f_{}n β is a summand in the recursive sum that expresses f_{}2n α , which happens if and only if 2n α 2 n β K, where K , and this is equivalent to 2β α belonging to .

Now ma_{z} α,a_{z} β^{}1 if and only if f ˜ n a_{z} β is a summand in the recursive sum that expresses f ˜ 2n a_{z} α , which happens if and only if 2n a_{z} α 2 n a_{z} β K̃, where K̃ ˜ . This means that a_{z} α 2β K̃, which gives 2β α .

Thus M_{}S^{1}M ˜ S, where

S ; ; ; ; ; ; ; \begin{matrix}0 & 0 & & 0 & 1 \\ 0 & 0 & & 1 & 0 \\ & & & & \\ 0 & 1 & & 0 & 0 \\ 1 & 0 & & 0 & 0 \end{matrix} ; ; ; ; ; ; ; ,

so M_{}and M ˜ are similar matrices and thus have the same characteristic polynomial, [4, 1.3.3]. Hence the denominator in (7) for is equal to the denominator in (7) for ˜ .

4 Open questions

A nicer formula for c , m than that given in Equation (7) is desired and seems likely. To that end, we have computed values of c for a variety of sets but have not been able to detect any patterns. Table 2 shows c , 1 for all sets of the form 0, 1, t , where 2 t 17, and we have obtained the following bounds on c , 1 for sets of this form.

Let t ℕ with t 1 and 0, 1, t . Choose k such that 2^{k} t 2^{k 1}. Recall that f_{}s is the number of ways to write s in the form

s _{i 0}^{}ϵ_{i}2^{i}, where ϵ_{i} 0, 1, t .

Then

s_{}r, 1 _{n 2^{r}}^{2^{r 1} 1} f_{}n c , 1 3^{r},

as shown in Theorem 4. Thus

_{s 1}^{2^{n} 1} f_{}s _{j 0}^{n 1} _{s 2^{j}}^{2^{j 1} 1} f_{}s _{j 0}^{n 1} c , 1 3^{j}

c , 1 \frac{3^{n} 1}{2} \frac{1}{2}c , 1 3^{n}.

Consider choosing ϵ_{i} 0, 1, t for 0 i n k 3 and ϵ_{i} 0, 1 for n k 2 i n 2. Then

_{i 0}^{n 2} ϵ_{i}2^{i} t t 2 t 2^{2}  t 2^{n k 3} 2^{n k 2} 2^{n k 1}  2^{n 2}
t 2^{n k 2} 2^{n 1} 1
2^{k 1} 2^{n k 2} 2^{n 1} 1
2^{n} 1
2^{n}.

There are 3^{n k 2} 2^{k 1} such sums, and each of them is counted in _{s 1}^{2^{n} 1} f_{}s . Thus

\frac{1}{2}c , 1 3^{n} 3^{n k 2} 2^{k 1} 3^{n} \frac{2^{k 1}}{3^{k 2}} ,

and so c , 1 \frac{2}{3} ^{k 2}.

Now suppose there exists some i_{0} n k such that ϵ_{i_{0}} t. Then

_{i 0}^{}ϵ_{i}2^{i} t 2^{i_{0}} t 2^{n k} 2^{k}2^{n k} 2^{n}.

Thus the sums counted in _{s 1}^{2^{n} 1} f_{}s all have the property that ϵ_{i} 0, 1 for n k i n 1, and there are 3^{n k} 2^{k} such sums. Hence 3^{n k} 2^{k} \frac{1}{2}c , 1 3^{n} and \frac{2^{k 1}}{3^{k}} c , 1 .

Combining the above, we see that

\frac{2^{k 1}}{3^{k}} \frac{2}{9} c , 1 \frac{2^{k 1}}{3^{k}} .

\begin{matrix} & c , 1 & N c , 1 & & c , 1 & N c , 1 \\ 0, 1, 2 & 1 & 1.000 & 0, 1, 3 & \frac{4}{5} & 0.800 \\ 0, 1, 4 & \frac{5}{8} & 0.625 & 0, 1, 5 & \frac{14}{25} & 0.560 \\ 0, 1, 6 & \frac{35}{71} & 0.493 & 0, 1, 7 & \frac{176}{391} & 0.450 \\ 0, 1, 8 & \frac{137}{338} & 0.405 & 0, 1, 9 & \frac{1448}{3775} & 0.384 \\ 0, 1, 10 & \frac{1990}{5527} & 0.360 & 0, 1, 11 & \frac{3223}{9476} & 0.340 \\ 0, 1, 12 & \frac{2020}{6283} & 0.322 & 0, 1, 13 & \frac{47228}{154123} & 0.306 \\ 0, 1, 14 & \frac{35624}{122411} & 0.291 & 0, 1, 15 & \frac{699224}{2501653} & 0.280 \\ 0, 1, 16 & \frac{68281}{256000} & 0.267 & 0, 1, 17 & \frac{38132531}{146988000} & 0.259 \end{matrix}

Table 2: c , 1 for all sets of the form 0, 1, t , where 2 t 17

.

To compare these bounds with Table 2, note that if 8 t 15, then k 3, and we have

0.132 c , 1 0.593

for 0, 1, t , with t in this range.

We have also computed c , 1 for some sets with 4 and 5, and that data is contained in Table 1. Larger sets have not been considered because computations become increasingly tedious as the cardinality of grows.

5 Acknowledgements

The author acknowledges support from National Science Foundation grant DMS 08-38434 “EMSW21-MCTP: Research Experience for Graduate Students”. The results in this paper were part of the author’s doctoral dissertation [2] at the University of Illinois at Urbana-Champaign. The author wishes to thank Professor Bruce Reznick for his time, ideas, and encouragement.

References

[1] K. Anders, Odd behavior in the coefficients of reciprocals of binary power series, Int. J. Number Theory 12 (2016), 635–648.

[2] K. Anders,  Properties of digital representations,  Ph.D. dis-
sertation,  University  of  Illinois  at  Urbana-Champaign,  2014,

https://www.ideals.illinois.edu/handle/2142/50698.

[3] K. Anders, M. Dennison, J. Lansing, and B. Reznick, Congruence properties of binary partition functions, Ann. Comb. 17 (2013), 15–26.

[4] R. Horn and C. Johnson, Matrix Analysis, 2nd ed., Cambridge Univ. Press, Cambridge, 2013.

[5] R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Encyclopedia of Mathematics and Its Applications, Vol. 20, Cambridge Univ. Press, Cambridge, 1997.

[6] B. Reznick, A Stern introduction to combinatorial number theory, Class notes, Math 595, University of Illinois at Urbana-Champaign, Spring 2012.

2010 Mathematics Subject Classification: Primary 11A63. Keywords: digital representation, non-standard binary representation, summatory function.

Received August 25 2015; revised versions received January 19 2016; March 11 2016; April 5 2016. Published in Journal of Integer Sequences, April 6 2016.

Return to Journal of Integer Sequences home page.