Keywords

AMS Classification Numbers:

1 Introduction

Let A be a subset of \(\mathbb {N} =\{0,1,2,\ldots \}\).

The characteristic function of A is defined by

$$\begin{aligned} \chi _A(n) = {\left\{ \begin{array}{ll} 1 &{} \text {if } n\in A , \\ 0 &{} \text {if } n\notin A. \end{array}\right. } \end{aligned}$$
(1)

The counting function of A is defined by

$$\begin{aligned} A(n)=\left| A\cap [0,n]\right| =\left| \left\{ a\in A:a\le n\right\} \right| . \end{aligned}$$
(2)

The representation function of A is defined by

$$\begin{aligned} r_{A}(n)=|\{(a,b)\in A\times A:a+b=n\}|. \end{aligned}$$
(3)

Here \(n \in {\mathbb N}\). But the three functions \(chi_A(n)\), A(n), \(r_A(n),\) can be extended to all real numbers \(x\in {\mathbb R}\), by simply replacing n by x in the above definitions.

Clearly, the functions \(\chi _A(n)\) and A(n) completely determine A, since the condition \(n\in A\) is equivalent to either conditions: \(\chi _A(n)=1\) or \(A(n)>A(n-1)\).

It is not as obvious that the function \(r_A(n)\) completely determines A too, but it does, and several authors have written about this topic. In particular, the consequences of the equality, or of the partial equality from some point on, of the representation functions \(r_A(n)\) and \(r_B(n)\) of two sets of natural numbers A and B have been studied rather extensively [1, 2, 12,13,14, 17, 22, 23]. Other research has focused on studying the properties of representation functions, trying to characterize the class of representation functions and to determine which functions belong to this class. Also, many outstanding open problems and conjectures have been made in this respect [3,4,5,6,7,8,9,10,11, 15, 16, 18,19,20,21]. In particular, Melvyn B. Nathanson highlights in one of his papers [18] the following problem:

What functions are representation functions?

The purpose of the present paper is twofold, first to establish relations between the three functions defined above, expressing each one of them in terms of each other one; and second, and more particularly, to attempt an answer to Nathanson’s question. We thus give an intrinsic characterization of representation functions by proving that a function \(f : {\mathbb N}\longrightarrow {\mathbb N}\) is the representation function of a subset A of \({\mathbb N}\) if and only if it satisfies the relation

$$ f(n) = \frac{1}{2} \left( n+1- \sum \limits _{k=0}^n (-1)^{f(2k) f(2(n-k))} \right) , $$

for all \(n \in {\mathbb N}\).

2 Preliminaries and Generating Series

We first note the following obvious relations between the characteristic and the counting functions of A:

$$\begin{aligned} A(n)=\sum \limits _{k=0}^n\chi _A(k), \end{aligned}$$
(4)

and

$$\begin{aligned} \chi _A(n) = A(n) - A(n-1), \end{aligned}$$
(5)

for all \(n\in \mathbb {N}\).

We then introduce the generating series of the three functions.

The generating series of \(\chi _A(n)\) is

$$\begin{aligned} f_A(X) = \sum \limits _{n=0}^{\infty }\chi _A(n)X^n = \sum \limits _{a\in A}X^a , \end{aligned}$$
(6)

also called the series associated with A.

The generating series of \(r_A(n)\) is

$$\begin{aligned} g_A(X) = \sum \limits _{n=0}^{\infty }r_A(n)X^n = \sum \limits _{n=0}^{\infty }\left( \sum \limits _{a,b\in A: a+b=n}1\right) X^n = \sum \limits _{a,b\in A}X^{a+b} = \left( \sum \limits _{a\in A}X^a\right) ^2 = f_A(X)^2 \end{aligned}$$
(7)

which is the square of the generating series \(f_A(X)\) of \(\chi _A(n)\).

The generating series of A(n) is

$$\begin{aligned} h_A(X)= \sum \limits _{n=0}^{\infty }A(n)X^n = \sum \limits _{n=0}^{\infty }\left( \sum \limits _{k =0}^n \chi _A(k) \right) X^n = \left( \sum \limits _{n=0}^{\infty }X^n \right) \left( \sum \limits _{n=0}^{\infty }\chi _A(n)X^n \right) = \dfrac{f_{A}(X)}{1-X}. \end{aligned}$$
(8)

3 Relations Between the Counting and Representation Functions

Squaring the generating series of the counting function, we get

$$\begin{aligned} \dfrac{g_{A}(X)}{(1-X)^2} = \left( \dfrac{f_A(X)}{1-X}\right) ^2 = \left( \sum \limits _{n=0}^{\infty }A(n)X^n \right) ^2 = \sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n A(k) A(n-k) \right) X^n. \end{aligned}$$
(9)

On the other hand, as \(g_A(X)\) is the generating series of \(r_A(n)\), and as

$$\begin{aligned} \dfrac{1}{(1-X)^2}=\dfrac{d}{dX}\left( \dfrac{1}{1-X}\right) = \sum \limits _{n=1}^{\infty } nX^{n-1} = \sum \limits _{n=0}^{\infty } (n+1) X^n, \end{aligned}$$
(10)

we also have

$$\begin{aligned} \dfrac{g_A(X)}{(1-X)^2}&= \left( \sum \limits _{j=0}^{\infty }(j+1)X^j \right) \left( \sum \limits _{k=0}^{\infty }r_A(k)X^k \right) =\sum \limits _{n=0}^{\infty }\left( \sum \limits _{j,k\in \mathbb N : j+k=n} (j+1) r_A(k) \right) X^n = \nonumber \\&=\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n (n-k+1) r_A(k) \right) X^n. \end{aligned}$$
(11)

Thus,

$$\begin{aligned} \dfrac{g_A(X)}{(1-X)^2}=\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n A(k) A(n-k) \right) X^n =\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n (n-k+1) r_A (k) \right) X^n. \end{aligned}$$
(12)

This yields the following result, which gives the first relation between A(n) and \(r_A(n)\).

Proposition 1

For every \(n\in \mathbb N\), we have

$$\begin{aligned} \sum \limits _{k=0}^n A(k)A(n-k)&=\sum \limits _{k=0}^n (n-k+1) r_A(k) = \nonumber \\&= (n+1) \sum \limits _{k=0}^n r_A(k) -\sum \limits _{k=0}^n kr_A(k), \ \end{aligned}$$
(13)

i.e.,

$$\begin{aligned} \sum \limits _{k=0}^n (n-k+1) r_A(k) =2\sum \limits _{0\le k<\tfrac{n}{2}} A(k) A(n-k) + \chi _{{\mathbb N}}\left( \dfrac{n}{2} \right) A\left( \dfrac{n}{2}\right) ^2. \end{aligned}$$
(14)

Corollary 1

For \(n\in \mathbb N\), we have

$$\begin{aligned} r_A (n) =2\sum \limits _{0\le k<\tfrac{n}{2}} A(k) A(n-k) + \chi _{{\mathbb N}} \left( \dfrac{n}{2} \right) A\left( \dfrac{n}{2} \right) ^2 - \sum \limits _{k=0}^{n-1} (n-k+1) r_A (k). \end{aligned}$$
(15)

Example 1

Applying the relation in the Corollary to \(n=0,1,2,\ldots \) in increasing order and back-substituting in terms of the A(n)’s alone, we get

\(r_A(0) = A(0)^2,\)

\(r_A(1) =2A(0)A(1) - 2A(0)^2,\)

\(r_A(2) = A(0)^2 - 4A(0)A(1) + 2A(0)A(2) + A(1)^2,\)

\(r_A(3) = 2A(0)A(1) - 4A(0)A(2) + 2A(0)A(3) - 2A(1)^2 + 2A(1)A(2)\)

$$\begin{aligned} r_A(4) =&\, 2A(0)A(2) - 4A(0)A(3) + 2A(0)A(4) +A(1)^2 - 4A(1)A(2) \,+ \qquad \\&+ 2A(1)A(3) + A(2)^2. \end{aligned}$$

Proposition 2

For any \(n\in {\mathbb N}\), we have

$$\begin{aligned} r_A(n)&=\sum \limits _{k=0}^n A(k)\left( A(n-k) -2A(n-k-1) +A(n-k-2) \right) = \nonumber \\&=\sum \limits _{j=0}^n \left( A(j)-2A(j-1) +A(j-2) \right) A(n-j). \end{aligned}$$
(16)

Proof

Using the generating series for \(r_A(n)\) and for A(n), we get

$$\begin{aligned} \sum \limits _{n=0}^{\infty } r_A(n)X^n&= g_A(X) = \left( \dfrac{f_A(X)}{1-X}\right) ^2 \left( 1-2X+X^2 \right) = \left( \sum \limits _{n=0}^{\infty }A(n)X^n\right) ^2\left( 1-2X+X^{2}\right) \\&=\left( \sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n A(k) A(n-k) \right) X^n \right) \left( 1-2X+X^2 \right) \\&=\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n A(k) A(n-k) \right) X^n -2\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n A(k) A(n-k) \right) X^{n+1} \\&+\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n A(k) A(n-k) \right) X^{n+2}\\&=\sum \limits _{n=0}^{\infty }\left( \sum \limits _{k=0}^n \left( A(k) A(n-k) -2A(k) A(n-1-k) +A(k) A(n-2-k) \right) \right) X^n. \end{aligned}$$

Hence, for all \(n\in {\mathbb N}\),

$$\begin{aligned} r_{A}(n)&=\sum \limits _{k=0}^n A(k)\cdot \left( A(n-k) -2A(n-k-1) +A(n-k-2) \right) \\&=\sum \limits _{j=0}^n \left( A(j)-2A(j-1) +A(j-2) \right) \cdot A(n-j). \end{aligned}$$

Corollary 2

For any \(n\in {\mathbb N}\), we have

$$\begin{aligned} r_A (n) =\sum \limits _{\begin{array}{c} j, k \in {\mathbb N}: \\ j+k \le n \end{array}} c_n (j, k) A(j)A(k), \end{aligned}$$
(17)

where

$$\begin{aligned} c_n (j, k) = {\left\{ \begin{array}{ll} 1, &{} \text {if } j+k =n \ \text {or} \ n-2 \\ -2, &{} \text {if } j+k =n-1 \\ 0, &{} \text {otherwise} \end{array}\right. } \quad . \end{aligned}$$
(18)

Proof

By Proposition 2,

$$\begin{aligned} r_A(n)&=\sum \limits _{k=0}^n A(k) A(n-k) - 2\sum \limits _{k=0}^n A(k) A(n-k-1) + \sum \limits _{k=0}^n A(k) A(n-k-2) = \\&=\sum \limits _{\begin{array}{c} j+k = n \end{array}} A(j)A(k) -2 \sum \limits _{\begin{array}{c} j+k = n-1 \end{array}} A(j)A(k) + \sum \limits _{\begin{array}{c} j+k = n-2 \end{array}} A(j)A(k) = \\&= \sum \limits _{\begin{array}{c} j+k \le n \end{array}} c_n (j, k) A(j)A(k). \end{aligned}$$

Corollary 3

For any \(n\in {\mathbb N}\), we have

$$\begin{aligned} r_A(n)&= \sum \limits _{j=0}^n \left( \chi _A (j) - \chi _A (j-1) \right) A(n-j) = \nonumber \\&=\sum \limits _{a\in A \smallsetminus (1+A) }A(n-a) -\sum \limits _{b\in (1+A) \smallsetminus A} A(n-b), \end{aligned}$$
(19)

the last two sums being obviously restricted to \(a\le n\) and \(b\le n.\)

Proof

For any \(k\in {\mathbb N}\), we have

$$\begin{aligned} A(k) = A(k-1) + \chi _A(k). \end{aligned}$$
(20)

Hence, for any \(j\in {\mathbb N}\),

$$\begin{aligned}&A(j)-2A(j-1) +A(j-2) = A(j)-A(j-1) -\left( A(j-1)-A(j-2) \right) = \nonumber \\&=\chi _A ( j) - \chi _A (j-1) = {\left\{ \begin{array}{ll} 0, \text {if } j-1,j\in A\text { or }j-1,j\notin A \\ 1, \text {if } j\in A,j-1\notin A \\ -1, \text {if } j\notin A,j-1\in A \end{array}\right. } \quad . \end{aligned}$$
(21)

This, in conjunction with Proposition 2, implies

$$\begin{aligned} r_A(n)&=\sum \limits _{j=0}^n \left( A(j)-2A(j-1) +A(j-2) \right) \cdot A(n-j) = \\&= \sum \limits _{j=0}^n \left( \chi _A (j) - \chi _A (j-1) \right) A(n-j) = \\&= \sum \limits _{\begin{array}{c} 0\le j\le n: \\ j\in A,\ j-1\notin A \end{array}} A( n-j) - \sum \limits _{\begin{array}{c} 0\le j\le n: \\ j-1\in A, \ j\notin A \end{array}} A(n-j) = \\&=\sum \limits _{a\in A\smallsetminus (1+A) } A(n-a) - \sum \limits _{b\in (1+A) \smallsetminus A} A(n-b) . \end{aligned}$$

Example 2

By Corollary 2, \(r_A (5) = \sum \limits _{\begin{array}{c} j, k \in {\mathbb N}: \\ j+k \le 5 \end{array}} c_5 (j, k) A(j)A(k)\), where

$$\begin{aligned} c_5 (j, k) = {\left\{ \begin{array}{ll} 1, &{} \text {if } j +k =5 \ \text {or} \ 3 \\ -2, &{} \text {if } j + k = 4 \\ 0, &{} \text {otherwise} \end{array}\right. } \quad . \end{aligned}$$

Hence,

$$\begin{aligned} r_A (5) =&\, 2A(0)A(3) -4A(0)A(4) +2A(0)A(5) +2A(1)A(2) -4A(1)A(3) \\&+2A(1)A(4)- 2A(2)^2 +2A(2)A(3). \end{aligned}$$

Similarly,

$$\begin{aligned} r_A (6) =&\,2A(0)A(4) -4A(0)A(5) +2A(0)A(6) +2A(1)A(3) -4A(1)A(4) \\&+2A(1)A(5)+A(2)^2 -4A(2)A(3) +2A(2)A(4) +A(3)^2. \end{aligned}$$
$$\begin{aligned} r_A(7) =&\,2A(0)A(5) -4A(0)A(6) +2A(0)A(7)+ 2A(1)A(4)- 4A(1)A(5) \\&+2A(1)A(6) +2A(2)A(3) -4A(2)A(4) +2A(2)A(5) -2A(3)^2 +2A(3)A(4). \end{aligned}$$

Remark 1

It follows from Corollary 2 that, for \(n\in {\mathbb N}\),

$$\begin{aligned} \sum \limits _{\begin{array}{c} j,k\in \mathbb {N} : \\ j+k\le n \end{array}} c_n (j,k) =\left\{ \begin{array}{c} 0,\text {if } \ n\ge 1 \\ 1,\text {if } \ n=0. \end{array} \right. \end{aligned}$$
(22)

Indeed, for \(n \ge 1\), we have

$$\begin{aligned} \sum \limits _{\begin{array}{c} j,k\in \mathbb {N}: \\ j+k\le n \end{array}} c_n (j,k)&=\sum \limits _{h=0}^n \sum \limits _{j+k=h} c_n (j,k) =\sum \limits _{j+k=n} c_n (j,k) +\sum \limits _{j+k=n-1} c_n (j,k) +\sum \limits _{j+k=n-2} c_n (j,k) = \\&=\sum \limits _{j+k=n} 1+\sum \limits _{j+k=n-1} ( -2) +\sum \limits _{j+k=n-2} 1=\sum \limits _{j=0}^{n} 1 -\sum \limits _{j=0}^{n-1} 2+ \sum \limits _{j=0}^{n-2} 1= \\&= (n+1)-2n+(n-1)=0. \end{aligned}$$

For \(n=0,\) the sum reduces to \(c_0 (0,0) =1.\) \(\square \)

Remark 2

For \(n\ge 1,\) we have

$$\begin{aligned} (1+A) (n) = A(n-1) = A(n) - \chi _A(n) = {\left\{ \begin{array}{ll} A(n), &{} \text {if } n\notin A \\ A(n)-1, &{} \text {if } n\in A. \end{array}\right. } \end{aligned}$$
(23)

So the last two sums in Corollary 3 have the same number of terms each if \(n\notin A,\) while the first of the two sums has one more term than the second one if \(n\in A.\)

Let \(I = A \cap (1+A), B=A \smallsetminus (1+A) = A \smallsetminus I\), and \(C= (1+A) \smallsetminus A = (1+A) \smallsetminus I\). Then,

$$\begin{aligned} C(n) = (1+A)(n) - I(n) = A(n) - I(n) - \chi _A(n) = B(n) - \chi _A(n). \end{aligned}$$
(24)

Let \(B[n] =B \cap [0,n] = \{ b_1< b_2< \cdots< b_{h-1} < b_h \}\) and \(C[n] = C \cap [0,n] = \{ c_1< c_2< \cdots < c_{h-1} \le c_h \}\), where \(c_h = c_{h-1}\) if \(n \in A\), and \(c_{h-1} < c_h\) if \(n \notin A\). In view of Corollary 3,

$$\begin{aligned} r_A(n)= \sum \limits _{b\in B[n]} A(n-b) - \sum \limits _{c\in C[n]} A(n-c), \end{aligned}$$
(25)

i.e.,

$$\begin{aligned} r_A(n)&= \sum \limits _{k=1}^h A(n-b_k) - \sum \limits _{k=1}^{h-1} A(n-c_k) - \left( 1- \chi _A(n) \right) A(n - c_h) = \nonumber \\&= \sum \limits _{k=1}^h \left( A(n-b_k) - A(n-c_k) \right) + \chi _A(n) A(n - c_h). \end{aligned}$$
(26)

Note also that \(b_k < c_k\) for \(1 \le k <h\) (and for \(k=h\) if \(n \notin A\)), since if \(A = \{ a_1< a_2< \cdots< a_n < \cdots \}\), then \(1+A = \{ a_1 +1< a_2 +1< \cdots< a_n +1 < \cdots \}\), and B (resp. C) is obtained from A (resp. \(1+A\)) by removing the same set I. It follows that \(n- b_k > n- c_k\) and therefore \(A(n- b_k) \ge A(n- c_k)\) for \(1 \le k <h\) (and for \(k=h\) if \(n \notin A\)).

Remark 3

We have

$$\begin{aligned} f_A (X) =\dfrac{1}{1-X}\left( \sum \limits _{a\in A\smallsetminus (1+A) } X^a - \sum \limits _{b\in (1+A) \smallsetminus A} X^b\right) . \end{aligned}$$
(27)

Indeed, letting \(I = A \cap (1+A)\), so that \(A \smallsetminus (1+A) = A \smallsetminus I\) and \((1+A) \smallsetminus A = (1+A) \smallsetminus I\), we have

$$\begin{aligned} (1-X) f_A(X)&= f_A(X) - Xf_A(X) = \sum \limits _{a\in A}X^a - \sum \limits _{a\in A}X^{a+1} = \sum \limits _{a\in A} X^a - \sum \limits _{b\in 1+A} X^b = \\&= \sum \limits _{a\in I} X^a + \sum \limits _{a\in A\smallsetminus I} X^a - \left( \sum \limits _{b\in I} X^b + \sum \limits _{b\in (1+A) \smallsetminus I} X^b \right) = \\&= \sum \limits _{a\in A\smallsetminus I} X^a - \sum \limits _{b\in (1+A) \smallsetminus I} X^b. \end{aligned}$$

4 Relations Between the Characteristic and the Representation Functions

Just as the counting function A(n) determines A, the number of representations function \(r_{A}(n)\) also determines A.

Indeed, as

$$ \sum \limits _{n=0}^{\infty }r_A(n)X^n = g_A(X) = f_A(X)^2, $$

we have

$$ f_A(X) =\sum \limits _{n=0}^{\infty }\chi _A(n)X^n = g_A(X)^{1/2}, $$

where if

$$ A=\{a_1<a_2<\cdots<a_n<\cdots \}, $$

then

$$f_A(X) = X^{a_1}\sum \limits _{n=1}^{\infty }X^{a_n - a_1} = X^{a_1} (1+X v(X)),$$

with the power series \(v(X) =\sum \limits _{n=2}^{\infty }X^{a_n - a_1 -1}\), so that

$$g_A(X) = X^{2a_1} (1+X u(X)),$$

with a power series u(X), and therefore

$$f_A(X) =X^{a_1} (1+Xu(X))^{1/2} = X^{a_1}\sum \limits _{k=0}^{\infty }\genfrac(){0.0pt}0{1/2}{k} X^k u(X)^k$$

is well defined. Moreover, replacing A by \(-a_1 +A= \{ a_n - a_1 : n\ge 1 \}\), we may assume that \(0\in A\), so that \(r_A (0) =1\), and

$$g_A(X) =\sum \limits _{n=0}^{\infty } r_A(n) X^n = 1+Xu(X),$$

with

$$u(X) =\sum \limits _{n=1}^{\infty } r_A(n) X^{n-1} = \sum \limits _{n=0}^{\infty }r_A(n+1)X^n.$$

Then,

$$\begin{aligned} f_A(X) =\sum \limits _{n=0}^{\infty }\chi _A(n) X^n = g_A(X)^{1/2} = (1+Xu(X))^{1/2} = \sum \limits _{k=0}^{\infty }\genfrac(){0.0pt}0{1/2}{k} X^k u(X)^k, \end{aligned}$$
(28)

where \(\genfrac(){0.0pt}0{x}{k}\) denotes the binomial coefficient, defined by

$$\begin{aligned} \genfrac(){0.0pt}0{x}{k} = \dfrac{x (x-1) (x-2) \cdots (x-k+1)}{k!}, \end{aligned}$$
(29)

for integers \(k\ge 1,\) while \(\genfrac(){0.0pt}0{x}{0}=1\).

Proposition 3

Assuming that \(0 \in A\), we have, for \(n \ge 1\),

$$\begin{aligned} \chi _A (n)&=\sum _{k=1}^n \genfrac(){0.0pt}0{1/2}{k} \sum \limits _{\begin{array}{c} (n_1,\ldots ,n_k)\in \left( {\mathbb N}^{*}\right) ^k: \\ n_1 +\cdots +n_k =n \end{array}} r_A(n_1)\cdots r_A (n_k) = \nonumber \\&= \sum _{k=1}^n (-1) ^{k-1}\dfrac{1\cdot 3\cdot 5\cdot \cdots \cdot (2k-3) }{k! 2^k} \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in (\mathbb {N}^{*})^k: \\ n_1 +\cdots + n_k =n \end{array}} r_A (n_1) \cdots r_A (n_k). \end{aligned}$$
(30)

Proof

We have \(f_A(X)=1+ \sum \limits _{n=1}^{\infty }\chi _A(n) X^n \), and

$$ g_A(X) = f_A(X)^2 = 1 + \sum _{n=1}^{\infty } r_A(n) X^n = 1 + Xu(X), $$

where u(X) is a power series with nonnegative integer coefficients. So

$$\begin{aligned} f_A(X)&= \left( 1 + Xu(X) \right) ^{1/2} = 1 + \sum _{k=1}^{\infty }\left( {\begin{array}{c}1/2\\ k\end{array}}\right) X^k u(X)^k \nonumber \\&= 1 + \sum _{k=1}^{\infty }\left( {\begin{array}{c}1/2\\ k\end{array}}\right) \left( \sum _{n=1}^{\infty } r_A(n) X^n \right) ^k. \end{aligned}$$
(31)

Moreover, for a positive integer \(k \in {\mathbb N}^*\), we have

$$\begin{aligned} \left( \sum _{n=1}^{\infty } r_A(n) X^n \right) ^k&= \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in \mathbb {N^*}^k \end{array}} r_A(n_1) \cdots r_A(n_k) X^{n_1+\cdots +n_k} = \nonumber \\&= \sum _{n=k}^{\infty } ( \sum _{k=1}^n \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in {{\mathbb N}^*}^k: \\ n_1+ \cdots + n_k =n \end{array}} r_A(n_1) \cdots r_A(n_k) ) X^n. \end{aligned}$$
(32)

Hence,

$$\begin{aligned} f_A(X)&= 1+ \sum \limits _{n=1}^{\infty }\chi _A(n) X^n = 1 + \sum _{k=1}^{\infty }\left( {\begin{array}{c}1/2\\ k\end{array}}\right) \left( \sum _{n=1}^{\infty } r_A(n) X^n\right) ^k = \nonumber \\&= 1 + \sum _{k=1}^{\infty }\left( {\begin{array}{c}1/2\\ k\end{array}}\right) \sum _{n=k}^{\infty } ( \sum _{k=1}^n \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in \mathbb {N^*}^k: \\ n_1+ \cdots + n_k =n \end{array}} r_A(n_1) \cdots r_A(n_k) ) X^n= \nonumber \\&= 1 + \sum _{n=1}^{\infty } ( \sum _{k=1}^n \left( {\begin{array}{c}1/2\\ k\end{array}}\right) \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in \mathbb {N^*}^k: \\ n_1+ \cdots + n_k =n \end{array}} r_A(n_1) \cdots r_A(n_k) ) X^n. \end{aligned}$$
(33)

Thus, for \(n \ge 1\),

$$ \chi _A(n) = \sum _{k=1}^n \left( {\begin{array}{c}1/2\\ k\end{array}}\right) \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in \mathbb {N^*}^k: \\ n_1+ \cdots + n_k =n \end{array}} r_A(n_1) \cdots r_A(n_k). $$

Furthermore, for \(k \ge 1\),

$$\begin{aligned} \genfrac(){0.0pt}0{1/2}{k}&= \dfrac{\left( 1/2\right) \left( -1/2\right) \left( -3/2\right) \cdots \left( 1/2-k+1\right) }{k!} = \nonumber \\&= (-1) ^{k-1} \dfrac{1\cdot 3\cdot 5\cdot \cdots \cdot (2k-3) }{k! 2^k}. \end{aligned}$$
(34)

Therefore, for \(n \ge 1\),

$$ \chi _A (n) = \sum _{k=1}^n (-1) ^{k-1}\dfrac{1\cdot 3\cdot 5\cdot \cdots \cdot (2k-3) }{k! 2^k} \sum \limits _{\begin{array}{c} (n_1, \ldots , n_k) \in (\mathbb {N}^{*})^k: \\ n_1 +\cdots + n_k =n \end{array}} r_A (n_1) \cdots r_A (n_k). $$

Example 3

\(\chi _A(1) = \dfrac{1}{2} r_A (1) ,\)

\(\chi _A (2) = \dfrac{1}{2} r_A (2) - \dfrac{1}{8} r_A (1)^2,\)

\(\chi _A (3) = \dfrac{1}{2} r_A (3) - \dfrac{1}{4} r_A (1) r_A (2) + \dfrac{1}{16} r_A (1)^3,\)

\(\chi _A (4) = \dfrac{1}{2} r_A (4) - \dfrac{1}{4} r_A (1) r_A (3) - \dfrac{1}{8} r_A (2)^2 + \dfrac{3}{16} r_A ( 1)^2 r_A (2) - \dfrac{5}{128} r_A (1)^4,\)

$$\begin{aligned} \chi _A (5) =&\dfrac{1}{2} r_A(5) {-} \dfrac{1}{4} r_A(1) r_A(4) {-} \dfrac{1}{4} r_A(2) r_A(3) + \dfrac{3}{16} r_A(1)^2 r_A(3) + \dfrac{3}{16} r_A(1) r_A(2)^2 \\&- \dfrac{5}{32} r_A(1)^3 r_A(2) + \dfrac{7}{256} r_A(1)^5. \end{aligned}$$

Corollary 4

For a subset A of \({\mathbb N}\) containing 0, the counting function of A is given by

$$\begin{aligned} A(x) = \sum \limits _{\begin{array}{c} n\in \mathbb {N} \\ n\le x \end{array}}\chi _A (n) = 1+\sum \limits _{\begin{array}{c} n\in \mathbb {N^*} \\ n\le x \end{array}} \sum _{k=1}^n \genfrac(){0.0pt}0{1/2}{k} \sum \limits _{\begin{array}{c} (n_{1},\ldots ,n_{k})\in (\mathbb {N}^{*}) ^k: \\ n_1+\cdots +n_k =n \end{array}} r_A (n_1)\cdots r_A(n_k), \end{aligned}$$
(35)

for \(x\ge 0.\)

Example 4

For \(n\ge 6,\)

$$\begin{aligned} \chi _A (n)&= \dfrac{1}{2} r_A(n) - \dfrac{1}{8} \sum \limits _{n_1 =1}^{n-1} r_A( n_1) r_A(n- n_1) + \nonumber \\&+ \dfrac{1}{16} \sum \limits _{n_1 =1}^{n-2} r_A( n_1) \sum \limits _{n_2=1}^{n-n_1 -1} r_A(n_2) r_A(n- n_1 -n_2) \nonumber \\&-\dfrac{5}{2^{7}}\sum \limits _{n_1=1}^{n-3} r_A( n_1) \sum \limits _{n_2=1}^{n-n_1-2} r_A(n_2) \sum \limits _{n_3 =1}^{n-n_1 -n_2 -1}r_A(n_3) r_A(n-n_1-n_2-n_3) \nonumber \\&+ \cdots \nonumber \\&+ (-1)^{n-1} \dfrac{1\cdot 3\cdot 5\cdot \cdots \cdot (2n-3) }{n!2^n} r_A(1)^n. \end{aligned}$$
(36)

Remark 4

Conversely, \(r_A(n)\) can be written in terms of \(\chi _A(n)\). Indeed, using Proposition 2 and the relations between the characteristic and the counting functions, we get, for \(n\in {\mathbb N}\),

$$\begin{aligned} r_A(n)&=\sum \limits _{k=0}^n A(k)\left( A(n-k) -2A(n-k-1) +A(n-k-2) \right) = \\&=\sum \limits _{k=0}^n \left( \sum \limits _{j=0}^k \chi _A(j) \right) \left( \sum \limits _{j=0}^{n-k}\chi _A(j) - 2\sum \limits _{j=0}^{n-k-1} \chi _A(j) + \sum \limits _{j=0}^{n-k-2}\chi _A(j) \right) = \\&= \sum \limits _{k=0}^n \left( \sum \limits _{j=0}^k \chi _A(j) \right) \left( \chi _A(n-k) - \chi _A(n-k-1) \right) , \end{aligned}$$

i.e.,

$$\begin{aligned} r_A (n) =\sum \limits _{k=0}^n \left( \chi _A(n-k) -\chi _A( n-k-1) \right) \sum \limits _{j=0}^k\chi _A(j), \end{aligned}$$
(37)

for all \(n\in {\mathbb N}\).

Alternatively,

$$\begin{aligned} r_A (n)&=\left| \{ 0\le j\le n: j,n-j\in A \} \right| = \left| \left\{ 0\le j\le n: \chi _A (j) = \chi _A (n-j) =1 \right\} \right| \nonumber \\&=\sum _{j=0}^n \chi _A(j) \chi _A(n-j). \end{aligned}$$
(38)

So

$$\begin{aligned} r_A (n) =\sum _{j=0}^n \chi _A(j) \chi _A(n-j) = 2\sum \limits _{\begin{array}{c} 0\le j<k\le n: \\ j+k=n \end{array}}\chi _A(j) \chi _A(k) +\chi _A \left( \dfrac{n}{2} \right) . \end{aligned}$$
(39)

5 Characterization of the Representation Function

Lemma 1

For any \(n \in {\mathbb N}\), we have

$$\begin{aligned} r_A (2n) \equiv \chi _A (n) \pmod 2. \end{aligned}$$
(40)

Proof

In view of (39),

$$\begin{aligned} r_A (2n) = 2\sum \limits _{\begin{array}{c} 0\le j<k\le n:\\ j+k=2n \end{array}}\chi _A(j) \chi _A(k) +\chi _A (n) \equiv \chi _A (n) \pmod 2. \end{aligned}$$

Corollary 5

For any \(n \in {\mathbb N}\), we have

$$\begin{aligned} n \in A \iff r_A (2n) \equiv 1 \pmod 2. \end{aligned}$$
(41)

Definition 1

For an integer \(a \in {\mathbb Z}\), let \(res_2(a)\) denote the least nonnegative residue of a modulo 2, i.e.,

$$\begin{aligned} res_2(a)= {\left\{ \begin{array}{ll} 0, &{} \text {if } a\equiv 0 \pmod 2 \\ 1, &{} \text {if } a\equiv 1 \pmod 2. \end{array}\right. } \end{aligned}$$
(42)

Remark 5

It is easy to verify that, for \(a, b \in {\mathbb Z}\), we have

$$\begin{aligned} res_2(a) = \frac{1- (-1)^a}{2}, \end{aligned}$$
(43)
$$\begin{aligned} res_2(ab) = res_2(a) res_2(b), \end{aligned}$$
(44)
$$\begin{aligned} res_2(a^n) = res_2(a)^n = res_2(a), \quad \text{ for }\ n\ge 1, \end{aligned}$$
(45)
$$\begin{aligned} res_2(a+b) = res_2 (a) + (-1)^a res_2 (b) = res_2 (b) + (-1)^b res_2 (a). \end{aligned}$$
(46)
$$\begin{aligned} res_2 (-a) = res_2(a), \quad res_2(a-b) = res_2(a+b), \end{aligned}$$
(47)

Remark 6

It follows from Lemma 1 and from Remark 5 that, for any \(n \in {\mathbb N}\), we have

$$\begin{aligned} \chi _A (n) = res_2 (r_A (2n)) = \frac{1- (-1)^{r_A (2n)}}{2}. \end{aligned}$$
(48)

Hence,

$$\begin{aligned} f_A(X) = \sum \limits _{n=0}^{\infty } \chi _A(n) X^n = \sum \limits _{n=0}^{\infty } \frac{1- (-1)^{r_A (2n)}}{2} X^n = \frac{1}{2} \left( \frac{1}{1-X} - \sum \limits _{n=0}^{\infty } (-1)^{r_A (2n)} X^n \right) . \end{aligned}$$
(49)

Moreover, for any \(n \in {\mathbb N}\),

$$\begin{aligned} A(n) = \sum \limits _{k=0}^n \chi _A(k) = \sum \limits _{k=0}^n res_2 (r_A (2k)) = \sum \limits _{k=0}^n \frac{1- (-1)^{r_A (2k)}}{2} = \frac{1}{2} \left( n+1- \sum \limits _{k=0}^n (-1)^{r_A (2k)} \right) , \end{aligned}$$
(50)

and

$$\begin{aligned} r_A(n)&= \sum \limits _{k=0}^n \chi _A(k) \chi _A(n-k) = \sum \limits _{k=0}^n res_2 (r_A (2k)) res_2 (r_A (2(n-k))) \nonumber \\&= \sum \limits _{k=0}^n res_2 (r_A (2k) r_A (2(n-k))) = \sum \limits _{k=0}^n \frac{1- (-1)^{r_A (2k) r_A (2(n-k))}}{2} \nonumber \\&= \frac{1}{2} \left( n+1- \sum \limits _{k=0}^n (-1)^{r_A (2k) r_A (2n-2k)} \right) . \end{aligned}$$
(51)

Thus, the values of \(r_A(2n) \pmod 2\) completely determine A and therefore completely determine all values of \(r_A(n)\). In other words, the representation function \(r_A\) of A is completely determined by the parity of its values at the even natural numbers.

Moreover, the relation (51) characterizes the representation function, as seen from the following Theorem.

Theorem 1

Let \(f : {\mathbb N}\longrightarrow {\mathbb N}\) be a function from the set of nonnegative integers \({\mathbb N}\) into itself, satisfying the relation

$$\begin{aligned} f(n) = \frac{1}{2} \left( n+1- \sum \limits _{k=0}^n (-1)^{f(2k) f(2(n-k))} \right) , \quad \text {for all} \ n \in {\mathbb N}. \end{aligned}$$
(52)

Then \(f = r_A\) is the representation function of the subset A of \({\mathbb N}\) defined by

$$\begin{aligned} A = \{ n \in {\mathbb N}: f(2n) \equiv 1 \pmod 2 \}. \end{aligned}$$
(53)

Proof

For any \(n \in {\mathbb N}\), we have

$$ \sum \limits _{k=0}^n (-1)^{f(2k) f(2(n-k))} = \sum \limits _{k \in I} 1 - \sum \limits _{k \in J} 1 = |I| - |J|, $$

where

$$ I = \{ k \in {\mathbb N}, \ 0 \le k \le n: f(2k) \equiv 0 \pmod 2 \ \ \text {or} \ \ f(2(n-k)) \equiv 0 \pmod 2 \} $$

and

$$ J = \{ k \in {\mathbb N}, \ 0 \le k \le n: f(2k) \equiv f(2(n-k)) \equiv 1 \pmod 2 \}. $$

Now, by definition of A, we have

$$ I = \{ k \in {\mathbb N}, \ 0 \le k \le n: k \not \in A \ \ \text {or} \ \ n-k \not \in A \} $$

and

$$ J = \{ k \in {\mathbb N}, \ 0 \le k \le n: k \in A \ \ \text {and} \ \ n-k \in A \}. $$

Clearly,

$$ I\cup J =\{ k \in {\mathbb N}: \ 0 \le k \le n \}, \quad \text {and} \quad I \cap J = \emptyset , $$

so that

$$ |I| + |J| = | I \cup J | = | \{ k \in {\mathbb N}: \ 0 \le k \le n \} | = n+1 $$

and

$$ \sum \limits _{k=0}^n (-1)^{f(2k) f(2(n-k))} = |I| - |J| = n+1 -2 |J|. $$

It follows from this, and from the defining relation (52) of f, that

$$ f(n) = \frac{1}{2} \left( n+1- \sum \limits _{k=0}^n (-1)^{f(2k) f(2(n-k))} \right) = |J|. $$

Moreover,

$$\begin{aligned} |J|&= | \{ k \in {\mathbb N}, \ 0 \le k \le n: k \in A \ \ \text {and} \ \ n-k \in A \} | = \\&= \sum \limits _{k \in A \ \text {and} \ (n-k) \in A} 1 = \sum _{k=0}^n \chi _A(k) \chi _A(n-k)= r_A (n), \end{aligned}$$

in view of (38).

Thus,

$$ f(n) = r_A(n),$$

for all \(n \in {\mathbb N}\).

Corollary 6

A function \(f : {\mathbb N}\longrightarrow {\mathbb N}\) is the representation function of a subset A of \({\mathbb N}\) if and only if it satisfies the relation

$$ f(n) = \frac{1}{2} \left( n+1- \sum \limits _{k=0}^n (-1)^{f(2k) f(2(n-k))} \right) , \quad \text {for all} \ n \in {\mathbb N}. $$

Proof

This follows from (51) in Remark 6 and from Theorem 1.

Remark 7

Corollary 6 provides a characterization of representation functions. It is easier to characterize the characteristic and the counting functions. Indeed, any function \(f : {\mathbb N}\longrightarrow \{ 0, 1 \}\) is the characteristic function of a unique subset A of \({\mathbb N}\), namely of \(A = f^{-1}(1)\). Also, any increasing (not necessarily strictly increasing) function \(f : {\mathbb N}\longrightarrow {\mathbb N}\) is the counting function of a unique subset A of \({\mathbb N}\), namely of \(A = \{n \in {\mathbb N}: f(n) > f(n-1) \}\), where we set, by definition, \(f(-1) =0\).