Finite Sequences Dominated by the Squares

L. Haddad 120 rue de Charonne 75011 Paris France

                    labib.haddad@wanadoo.fr

C. Helou Department of Mathematics Pennsylvania State University 25 Yearsley Mill Road Media, PA 19063 USA

                         cxh22@psu.edu

Abstract We evaluate the number u(n) of length-n finite sequences (a_{k})_{1≤k≤n} of natural numbers that satisfy the inequality a_{k} ≤ k^{2} for all k. We thus determine two recurrence relations for u(n) by two different methods, and we give an explicit expression in closed form for it.

1 Introduction

The general Erdős-Turán conjecture([2, 1, 5]) states that if A = {a_{1} < a_{2} < ⋯ < a_{n} < ⋯ } is an infinite subset of the set ℕ = {0, 1, 2, 3 …} of natural numbers satisfying a_{n} ≤ cn^{2} for all integers n ≥ 1, with any real constant c > 0, then the number of representations function associated with A, defined by r(A, n) = |{(a_{i}, a_{j}) ∈ A × A : a_{i} + a_{j} = n}|, for n ∈ ℕ, is unbounded. In a previous paper ([3]), we established that it is enough to prove the conjecture for sequences satisfying a_{n} ≤ n^{2} for all n ≥ 1. More recently, we undertook a quantitative exploration of the conjecture ([4]) by studying a function ψ(n) defined on the set A(n) of all sequences A = {a_{1} < a_{2} < ⋯ < a_{n}} of n elements in ℕ dominated by the squares, i.e., satisfying a_{k} ≤ k^{2} for 1 ≤ k ≤ n. In the process, a natural question that came up was the determination of the number u(n) = |A(n)| of such sequences. It proved to be a non-trivial combinatorial problem of intrinsic interest. We here present two solutions to this problem by two different methods which agree numerically.

We first introduce two auxiliary sequences of numbers u (n, t) = |A(n, t)| and v (n, t) = |A(n|t)|, depending on two integer parameters n, t ∈ ℕ, in terms of which u(n) can be simply expressed, where A(n, t) (resp. A(n|t)) is the set of all subsets of A(n) contained in the interval [0, t] (resp. whose largest element a_{n} = t). We thus prove ((9) and (11)) that

u(n) = ∑_{t=n−1}^{n^{2}} v(n, t) = u(n, n^{2} − k) + k · u(n − 1), for n ≥ 1, 1 ≤ k ≤ 2n − 1.

These double sequences (u(n, t))_{n,t} and (v (n, t))_{n,t} have properties of intrinsic interest. For instance, they satisfy the relations ((13) and (14) )

u(n, t) = u(n, t − 1) + u(n − 1, t − 1), v(n, t) = v(n, t − 1) + v(n − 1, t − 1), for 1 ≤ t ≤ n^{2}.

These relations are similar to the ones satisfied by the binomial coefficients, but they are subject to the restriction t ≤ n^{2}. It is thus possible to construct for u(n, t) and v(n, t) analogues of Pascal triangle.

As for the main sequence u(n), we obtain two different recurrence formulas for it by two different methods, namely ((22) and (32)), for n ≥ 2,

u(n) = ∑_{k=1}^{n}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k);

and

u(n) = \binom{n^{2}}{n − 1} + \binom{n^{2} − 1}{n − 1} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2}}{n − k + 1}u (k − 1) .

We also establish an explicit expression in “closed form” for u(n), namely ((37))

u(k − 1) = \frac{Δ_{n}(k)}{Δ_{n}}, for 2 ≤ k ≤ n − 1,

where Δ_{n} is the (n − 2) × (n − 2) determinant

Δ_{n} = det ((a_{n}(h, k))\begin{matrix}0≤h≤n−3 \\ 2≤k≤n−1 \end{matrix}) ,

and Δ_{n}(k) is the determinant obtained by replacing in Δ_{n} the k-th column by the column (b_{n}(h))_{0≤h≤n−3}, with

a_{n}(h, k) = \binom{n^{2} − k^{2} + h − 1}{n − k − 1}, and b_{n}(h) = \binom{n^{2} + h − 1}{n − 3} + \binom{n^{2} + h − 2}{n − 3},

for 0 ≤ h ≤ n − 3 and 2 ≤ k ≤ n − 1. However this expression is not practical, since the size of the determinant grows with n.

The sequence (u(n))_{n∈ℕ} appears in N. J. A. Sloane’s database, The On-line Encyclopedia of Integer Sequences (OEIS) [6], as \underline{A242105}.

2 The auxiliary double sequences

For any n ∈ ℕ, let A(n) be the set of all subsets A = {a_{1} < a_{2} < ⋯ < a_{n}} of ℕ of cardinality |A| = n, satisfying a_{k} ≤ k^{2} for 1 ≤ k ≤ n. Also, for any n, t ∈ ℕ, let

A(n, t) = {A ∈ A(n) : A ⊂ [0, t]} ,

and

A(n|t) = {A ∈ A(n) : max (A) = t} .

Further, let u (n) = |A (n)| , u (n, t) = |A(n, t)|, and v (n, t) = |A(n|t)| .

Obviously,

u(0) = 1,  u(1) = 2.  (1)

It follows from the definitions that if n > 0 and A = {a_{1} < ⋯ < a_{n}} ∈ A(n), then

k − 1 ≤ a_{k} ≤ k^{2}, for 1 ≤ k ≤ n.  (2)

It is not difficult to see that

u(n, t) = \begin{cases}0, & if 0 ≤ t < n − 1; \\ 1, & if n = 0 or (n = 1, t = 0); \\ u(n), & if t ≥ n^{2} ≥ 1. \end{cases}  (3)

Also,

v(n, t) = \begin{cases}0, & if n = 0 or (t = 0, n ≠ 1) or t < n − 1 or t > n^{2}; \\ 1, & if n = 1 and t = 0, 1. \end{cases}  (4)

Moreover,

u(n, n − 1) = v (n, n − 1) = 1, for n ≥ 1.  (5)

Lemma 1. For n, t ∈ ℕ, we have

v(n, t) = \begin{cases}u(n − 1, t − 1), & if t ≤ n^{2}; \\ 0, & if t > n^{2} . \end{cases}  (6)

Proof. If t ≤ n^{2}, then A(n|t) = {A ∪ {t} : A ∈ A(n − 1, t − 1)}, and therefore v(n, t) = u (n − 1, t − 1). For t > n^{2}, the result follows from (4).

Remark 2. It follows from (6) and (3) that

v(n, t) = u (n − 1, t − 1) = u (n − 1) , for (n − 1)^{2} < t ≤ n^{2}.  (7)

Therefore

u(n) = v (n + 1, t) , for n^{2} < t ≤ (n + 1)^{2}.  (8)

Lemma 3. For n ≥ 1, we have

u(n) = ∑_{t=n−1}^{n^{2}} v(n, t) = ∑_{t=0}^{∞} v(n, t).  (9)

Proof. It follows from (2) that A(n) = ⋃_{t=n−1}^{n^{2}} A(n|t), a union of pairwise disjoint sets. Hence the first equality. The second equality follows from (4). Lemma 4. For any n, s, t ∈ ℕ such that s < t, we have

u(n, t) = u(n, s) + ∑_{k=s+1}^{t} v(n, k).  (10)

Proof. This follows from the simple equality A(n, t) = A(n, s) ⋃ ( ⋃_{k=s+1}^{t} A(n|k)), with a union of pairwise disjoint sets. Lemma 5. For n ≥ 1 and 1 ≤ k ≤ 2n − 1, we have

u(n) = u(n, n^{2} − k) + k · u(n − 1).  (11)

Proof. By (3) and (10), we have

u(n) = u(n, n^{2}) = u(n, n^{2} − k) + ∑_{j=n^{2}−k+1}^{n^{2}} v(n, j).

Moreover, for 1 ≤ k ≤ 2n − 1 and n^{2} − k < j ≤ n^{2}, we have (n − 1)^{2} < j ≤ n^{2}, and therefore v(n, j) = u(n − 1), by (7). Hence the result. Remark 6. It follows from (10) with s = t − 1, that, for n ≥ 0, t ≥ 1, we have

u(n, t) = u (n, t − 1) + v (n, t) .  (12)

Lemma 7. For 1 ≤ t ≤ n^{2}, we have

u(n, t) = u(n, t − 1) + u(n − 1, t − 1).  (13)

Proof. We clearly have

A(n, t) = A(n|t) ∪ A(n, t − 1),

and

A(n|t) ∩ A(n, t − 1) = ∅.

Hence

u(n, t) = |A(n, t)| = |A(n|t)| + |A(n, t − 1)| = v(n, t) + u(n, t − 1).

Moreover, by (6),

v(n, t) = u(n − 1, t − 1).

The result follows immediately. Lemma 8. For 1 ≤ t ≤ n^{2}, we have

v(n, t) = v(n, t − 1) + v(n − 1, t − 1).  (14)

Proof. It can be easily verified that the relation holds for t = 1. So we may assume that 2 ≤ t ≤ n^{2}. We have a bijection

f : A(n|t) → A(n − 1|t − 1) ∪ A(n − 1, t − 2)

which, to A = {a_{1} < a_{2} < ⋯ < a_{n}}, with a_{n} = t, makes correspond

f(A) = A \ {t} = {a_{1} < a_{2} < ⋯ < a_{n−1}}

. And we have

A(n − 1|t − 1) ∩ A(n − 1, t − 2) = ∅.

Hence v(n, t) = |A(n|t)| = |A(n − 1|t − 1)| + |A(n − 1, t − 2)| = v(n − 1, t − 1) + u(n − 1, t − 2). Moreover, by (6), v(n, t − 1) = u(n − 1, t − 2). The result follows immediately. Lemma 9. For n, t ≥ 1, we have

u(n, t) − u(n, t − 1) = \begin{cases}u(n − 1, t − 1), & if t ≤ n^{2}; \\ 0, & if t > n^{2}. \end{cases}  (15)

Proof. By (12), we have u(n, t) − u (n, t − 1) = v (n, t), and the result follows from (6). Lemma 10. For n, t ≥ 1, we have

v(n, t) − v(n, t − 1) − v (n − 1, t − 1) = \begin{cases}−u(n − 1), & if t = n^{2} + 1; \\ 0 & if t ≠ n^{2} + 1. \end{cases}  (16)

Proof. If t = n^{2} + 1, then, by (4) and (7),

v(n, n^{2} + 1) − v(n, n^{2}) − v(n − 1, n^{2}) = −u(n − 1).

If t > n^{2} + 1, then, by (4), all terms on the left are = 0 and the last case holds.

If 1 ≤ t ≤ n^{2}, then, by (6), v(n, t) = u(n − 1, t − 1) and v(n, t − 1) = u (n − 1, t − 2); and, by (12), v (n − 1, t − 1) = u(n − 1, t − 1) − u(n − 1, t − 2). Therefore

v(n, t) − v(n, t − 1) − v (n − 1, t − 1) = 0.

Hence the result.

Example 11. Using the relation (14), we can construct an analogue of Pascal’s triangle for the numbers v(n, t). We here give the first few rows of such a table.

\begin{matrix}v(n, t) & n = 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ t = 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 2 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 2 & 5 & 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 7 & 9 & 5 & 1 & 0 & 0 & 0 & 0 \\ 6 & 0 & 0 & 7 & 16 & 14 & 6 & 1 & 0 & 0 & 0 \\ 7 & 0 & 0 & 7 & 23 & 30 & 20 & 7 & 1 & 0 & 0 \\ 8 & 0 & 0 & 7 & 30 & 53 & 50 & 27 & 8 & 1 & 0 \\ 9 & 0 & 0 & 7 & 37 & 83 & 103 & 77 & 35 & 9 & 1 \\ 10 & 0 & 0 & 0 & 44 & 120 & 186 & 180 & 112 & 44 & 10 \\ 11 & 0 & 0 & 0 & 44 & 164 & 306 & 366 & 292 & 156 & 54 \\ 12 & 0 & 0 & 0 & 44 & 208 & 470 & 672 & 658 & 448 & 210 \\ 13 & 0 & 0 & 0 & 44 & 252 & 678 & 1142 & 1330 & 1106 & 658 \\ 14 & 0 & 0 & 0 & 44 & 296 & 930 & 1820 & 2472 & 2436 & 1764 \\ 15 & 0 & 0 & 0 & 44 & 340 & 1226 & 2750 & 4292 & 4908 & 4200 \\ 16 & 0 & 0 & 0 & 44 & 384 & 1566 & 3976 & 7042 & 9200 & 9108 \\ 17 & 0 & 0 & 0 & 0 & 428 & 1950 & 5542 & 11018 & 16242 & 18308 \\ 18 & 0 & 0 & 0 & 0 & 428 & 2378 & 7492 & 16560 & 27260 & 34550 \\ 19 & 0 & 0 & 0 & 0 & 428 & 2806 & 9870 & 24052 & 43820 & 61810 \\ 20 & 0 & 0 & 0 & 0 & 428 & 3234 & 12676 & 33922 & 67872 & 105630 \end{matrix}

Proposition 12. For k, n, t ∈ ℕ such that 1 ≤ k ≤ n and k ≤ t ≤ (n − k + 1)^{2} + k − 1, we have

u(n, t) = ∑_{i=0}^{k} \binom{k}{i}u(n − i, t − k).  (17)

Proof. For a given n ≥ 1, the proof is by induction on k.

For k = 1, the equality amounts to u(n, t) = u(n, t − 1) + u(n − 1, t − 1), which is true for 1 ≤ t ≤ n^{2}, by (13).

Assume the equality holds for some 1 ≤ k < n and all k ≤ t ≤ (n − k + 1)^{2} + k − 1. Then, for k + 1 ≤ t ≤ (n − k)^{2} + k, we have, by (13),

u(n − i, t − k) = u(n − i, t − k − 1) + u(n − i − 1, t − k − 1),

for 0 ≤ i ≤ k. Hence

u(n, t) = ∑_{i=0}^{k} \binom{k}{i}u(n − i, t − k) = ∑_{i=0}^{k} \binom{k}{i} (u(n − i, t − k − 1) + u(n − i − 1, t − k − 1)) =

= ∑_{i=0}^{k} \binom{k}{i}u(n − i, t − k − 1) + ∑_{j=1}^{k+1} \binom{k}{j − 1}u(n − j, t − k − 1) =

= ∑_{i=1}^{k} (\binom{k}{i} + \binom{k}{i − 1}) u(n − i, t − k − 1)+

+ u(n, t − k − 1) + u(n − k − 1, t − k − 1)

= ∑_{i=0}^{k+1} \binom{k + 1}{i}u(n − i, t − (k + 1)), for k + 1 ≤ t ≤ (n − k)^{2} + k.

So the equality holds for k + 1 and all k + 1 ≤ t ≤ (n − k)^{2} + k. This completes the induction.

3 The main sequence (u (n))_{n≥0}

We now propose to establish a recurrence formula for the numbers u(n). In the course of the work, we will need the following summation formulas for binomial coefficients.

Lemma 13. For all integers N ≥ m ≥ 0, we have

∑_{k=m}^{N} \binom{k}{m} = \binom{N + 1}{m + 1}.  (18)

Proof. The proof is by a simple induction on N, using the fundamental recurrence for binomial coefficients

\binom{N}{m} + \binom{N}{m + 1} = \binom{N + 1}{m + 1}.

Corollary 14. For all integers N ≥ M ≥ m ≥ 0, we have

∑_{k=M}^{N} \binom{k}{m} = ∑_{k=m}^{N} \binom{k}{m} − ∑_{k=m}^{M−1} \binom{k}{m} = \binom{N + 1}{m + 1} − \binom{M}{m + 1}.  (19)

Remark 15. In the remainder of this section, we set a_{0} = 0. Lemma 16. For n ≥ 1, we have

u (n) = ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n}=a_{n−1}+1}^{n^{2}} 1.  (20)

Proof. By definition, A(n) consists of all subsets A = {a_{1} < a_{2} < ⋯ < a_{n}} of ℕ satisfying

0 ≤ a_{1} ≤ 1, a_{1} + 1 ≤ a_{2} ≤ 4, a_{2} + 1 ≤ a_{3} ≤ 9, …, a_{n−1} + 1 ≤ a_{n} ≤ n^{2}.

The stated relation for u (n) = |A (n)| follows immediately. Theorem 17. For n ≥ 2 and 1 ≤ h ≤ n − 1, we have

u(n) = ∑_{k=1}^{h}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k)+
+ (−1)^{h} ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h}=a_{n−h−1}+1}^{(n−h)^{2}} \binom{a_{n−h} + h − 1}{h}.  (21)

Proof. For a fixed n ≥ 2, the proof is by induction on h.

First, note that the truth of (21) for h = 1 follows immediately from (20)

Assume now, by induction, that (21) holds for some 1 ≤ h < n − 1. By (19), we have

∑_{a_{n−h}=a_{n−h−1}+1}^{(n−h)^{2}} \binom{a_{n−h} + h − 1}{h} = ∑_{k=a_{n−h−1}+h}^{(n−h)^{2}+h−1} \binom{k}{h} = \binom{(n − h)^{2} + h}{h + 1} − \binom{a_{n−h−1} + h}{h + 1},

and substituting this into (21) yields

u(n) = ∑_{k=1}^{h}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k)+

+ (−1)^{h} ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h−1}=a_{n−h−2}+1}^{(n−h−1)^{2}} (\binom{(n − h)^{2} + h}{h + 1} − \binom{a_{n−h−1} + h}{h + 1}) =

= ∑_{k=1}^{h}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k)+

+ (−1)^{h} \binom{(n − h)^{2} + h}{h + 1} ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h−1}=a_{n−h−2}+1}^{(n−h−1)^{2}} 1+

+ (−1)^{h+1} ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h−1}=a_{n−h−2}+1}^{(n−h−1)^{2}} \binom{a_{n−h−1} + h}{h + 1}.

Moreover, by (20),

∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h−1}=a_{n−h−2}+1}^{(n−h−1)^{2}} 1 = u(n − h − 1).

Hence

u(n) = ∑_{k=1}^{h}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k) + (−1)^{h} \binom{(n − h)^{2} + h}{h + 1}u(n − h − 1)+

+ (−1)^{h+1} ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h−1}=a_{n−h−2}+1}^{(n−h−1)^{2}} \binom{a_{n−h−1} + h}{h + 1} =

= ∑_{k=1}^{h+1}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k)+

(−1)^{h+1} ∑_{a_{1}=0}^{1} ∑_{a_{2}=a_{1}+1}^{4} ⋯ ∑_{a_{n−h−1}=a_{n−h−2}+1}^{(n−h−1)^{2}} \binom{a_{n−h−1} + h}{h + 1},

which is just the expression (21) for h+1 replacing h. This completes the proof by induction of (21).

Corollary 18. For n ≥ 2, we have

u(n) = ∑_{k=1}^{n}(−1)^{k−1}\binom{(n − k + 1)^{2} + k − 1}{k}u(n − k).  (22)

\begin{matrix}n & u(n) \\ 0 & 1 \\ 1 & 2 \\ 2 & 7 \\ 3 & 44 \\ 4 & 428 \\ 5 & 5802 \\ 6 & 102322 \\ 7 & 2239844 \\ 8 & 58849332 \\ 9 & 1810039960 \\ 10 & 63930543419 \end{matrix}

Table 1: First few values of u(n)

Proof. Taking h = n − 1, the multiple sum in (21) reduces to

(−1)^{n−1} ∑_{a_{1}=0}^{1} \binom{a_{1} + n − 2}{n − 1} = (−1)^{n−1} = (−1)^{n−1}u(0).

Substituting this into (21) yields the desired expression for u(n).

Example 19. Using (22) and (1), we can compute u(n) recursively. We thus obtain the data in Table 1.

More values of u(n) can be found in \underline{A242105} of the OEIS ([6]).

4 An alternative approach

Definition 20. For t ∈ ℕ, let t^{∗} = ⌈\sqrt{t}⌉ be the least integer ≥ \sqrt{t}, so that t^{∗} = m if and only if (m − 1)^{2} < t ≤ m^{2} for some m ∈ ℕ, and let

p_{t}(x) = ∑_{n=t^{∗}}^{t+1} v(n, t)x^{n−t^{∗}} = x^{t+1−t^{∗}} + ∑_{n=t^{∗}}^{t} v(n, t)x^{n−t^{∗}}.  (23)

Proposition 21. For t ≥ 1, the polynomials p_{t} satisfy the following recurrence formula.

p_{t+1}(x) = \begin{cases}\frac{1}{x} ((x + 1) p_{t}(x) − u (m − 1)) , & if t = m^{2}, with m ∈ ℕ; \\ (x + 1) p_{t}(x), & otherwise. \end{cases}  (24)

Proof. Note first that if n ≥ (t + 1)^{∗} then n^{2} > t, and that by (14), v (n, t + 1) = v(n, t) + v(n − 1, t), for 0 ≤ t < n^{2}. Hence

p_{t+1}(x) = ∑_{n=(t+1)^{∗}}^{t+2} v(n, t + 1)x^{n−(t+1)^{∗}} = ∑_{n=(t+1)^{∗}}^{t+2} (v(n, t) + v(n − 1, t)) x^{n−(t+1)^{∗}} =

= ∑_{n=(t+1)^{∗}}^{t+2} v(n, t)x^{n−(t+1)^{∗}} + ∑_{n=(t+1)^{∗}−1}^{t+1} v(n, t)x^{n+1−(t+1)^{∗}}.

If t = m^{2}, then t^{∗} = m and (t + 1)^{∗} = m + 1, so that

∑_{n=(t+1)^{∗}}^{t+2} v(n, t)x^{n−(t+1)^{∗}} = ∑_{n=m+1}^{m^{2}+2} v(n, m^{2})x^{n−m−1} = \frac{1}{x} ∑_{n=t^{∗}+1}^{t+2} v(n, t)x^{n−t^{∗}} =

= \frac{1}{x} (p_{t}(x) − v (m, m^{2}) + v (m^{2} + 2, m^{2}) x^{m^{2}+2−m}) = \frac{1}{x} (p_{t}(x) − u (m − 1)) ,

since v (m, m^{2}) = u(m − 1) by (8), and v (m^{2} + 2, m^{2}) = 0 by (4), and

∑_{n=(t+1)^{∗}−1}^{t+1} v(n, t)x^{n+1−(t+1)^{∗}} = ∑_{n=m}^{m^{2}+1} v(n, m^{2})x^{n−m} = ∑_{n=t^{∗}}^{t+1} v(n, t)x^{n−t^{∗}} = p_{t}(x).

Therefore, in the case t = m^{2}, we have

p_{t+1}(x) = \frac{1}{x} (p_{t}(x) − u (m − 1)) + p_{t}(x) = \frac{1}{x} ((x + 1) p_{t}(x) − u (m − 1)) .

Otherwise, if t is not a square, i.e., m^{2} < t < (m + 1)^{2}, with m ∈ ℕ, then t^{∗} = (t + 1)^{∗} = m + 1, so that

∑_{n=(t+1)^{∗}}^{t+2} v(n, t)x^{n−(t+1)^{∗}} = ∑_{n=t^{∗}}^{t+2} v(n, t)x^{n−t^{∗}} = p_{t}(x) + v (t + 2, t) x^{t+2−t^{∗}} = p_{t}(x),

since v (t + 2, t) = 0 by (4); and

∑_{n=(t+1)^{∗}−1}^{t+1} v(n, t)x^{n+1−(t+1)^{∗}} = ∑_{n=t^{∗}−1}^{t+1} v(n, t)x^{n+1−t^{∗}} = x ∑_{n=t^{∗}−1}^{t+1} v(n, t)x^{n−t^{∗}} =
= x (p_{t}(x) + v (t^{∗} − 1, t) x^{−1}) = xp_{t} (x) ,

since v (t^{∗} − 1, t) = v (m, t) = 0, by (4). Therefore, in this case, we have

p_{t+1}(x) = p_{t}(x) + xp_{t}(x) = (x + 1) p_{t}(x).

Corollary 22. For n ≥ 1 and 1 ≤ h ≤ 2n + 1, we have

p_{n^{2}+h} (x) = \frac{1}{x} ((x + 1)^{h} p_{n^{2}}(x) − u (n − 1) (x + 1)^{h−1}) .  (25)

Proof. The proof is by induction on h. By (24), p_{n^{2}+1} (x) = \frac{1}{x} ((x + 1) p_{n^{2}}(x) − u (n − 1)), so that the property holds for h = 1. Assume, by induction that it holds for some 1 ≤ h ≤ 2n. Then, by (24) and the induction assumption,

p_{n^{2}+h+1} (x) = (x + 1) p_{n^{2}+h} (x) = \frac{x + 1}{x} ((x + 1)^{h} p_{n^{2}}(x) − u (n − 1) (x + 1)^{h−1}) =

= \frac{1}{x} ((x + 1)^{h+1} p_{n^{2}}(x) − u (n − 1) (x + 1)^{h}) ,

which shows that the result holds for h + 1 and completes the induction. Example 23. We have

p_{0}(x) = x,  p_{1}(x) = x + 1,  p_{2}(x) = x + 2,
p_{3}(x) = x^{2} + 3x + 2,  p_{4}(x) = x^{3} + 4x^{2} + 5x + 2,  p_{5}(x) = x^{3} + 5x^{2} + 9x + 7.

Definition 24. For any integer n ≥ 2, let

T_{n}(x) = ∑_{k=2}^{n−1} u (k − 1) x^{k−2} (x + 1)^{n^{2}−k^{2}−1} .

Example 25. We have

T_{2} (x) = 0, T_{3} (x) = 2(x + 1)^{4},

T_{4}(x) = 2x^{11}+22x^{10}+110x^{9}+330x^{8}+667x^{7}+966x^{6}+1029x^{5}+800x^{4}+435x^{3}+152x^{2}+29x+2. Lemma 26. For n ≥ 2, we have

T_{n+1}(x) = (x + 1)^{2n+1} T_{n} (x) + u (n − 1) x^{n−2} (x + 1)^{2n} .  (26)

Proof. By definition,

T_{n+1}(x) = ∑_{k=2}^{n} u (k − 1) x^{k−2} (x + 1)^{(n+1)^{2}−k^{2}−1} = ∑_{k=2}^{n} u (k − 1) x^{k−2} (x + 1)^{n^{2}+2n−k^{2}}

= (x + 1)^{2n+1} ∑_{k=2}^{n−1} u (k − 1) x^{k−2} (x + 1)^{n^{2}−k^{2}−1} + u(n − 1)x^{n−2} (x + 1)^{2n} =

= (x + 1)^{2n+1} T_{n} (x) + u (n − 1) x^{n−2} (x + 1)^{2n} .

Lemma 27. For n ≥ 2, we have

p_{n^{2}} (x) = \frac{(x + 1)^{n^{2}−1} + (x + 1)^{n^{2}−2} − T_{n}(x)}{x^{n−2}}.  (27)

Proof. The proof is by induction on n. Using the Examples given above, it is easily verified that p_{4}(x) = (x + 1)^{3} + (x + 1)^{2} − T_{2} (x), so that the relation holds for n = 2.

Assume inductively that it holds for n. Then, by (25), the induction assumption and (26), we have

xp_{(n+1)^{2}}(x) = xp_{n^{2}+2n+1} (x) = (x + 1)^{2n+1} p_{n^{2}}(x) − u (n − 1) (x + 1)^{2n} =

= (x + 1)^{2n+1} \frac{(x + 1)^{n^{2}−1} + (x + 1)^{n^{2}−2} − T_{n}(x)}{x^{n−2}} − u (n − 1) (x + 1)^{2n} .

Therefore

x^{n−1}p_{(n+1)^{2}}(x) = (x + 1)^{n^{2}+2n} + (x + 1)^{n^{2}+2n−1} − (x + 1)^{2n+1} T_{n}(x)
− u (n − 1) x^{n−2} (x + 1)^{2n} = (x + 1)^{(n+1)^{2}−1} + (x + 1)^{(n+1)^{2}−2} − T_{n+1}(x).

Thus the relation holds for n + 1.

Corollary 28. For n ≥ 2 and 1 ≤ h ≤ 2n + 1, we have

p_{n^{2}+h}(x) =  (28)

= \frac{(x + 1)^{n^{2}+h−1} + (x + 1)^{n^{2}+h−2} − (x + 1)^{h} T_{n} (x) − u (n − 1) x^{n−2} (x + 1)^{h−1}}{x^{n−1}} .

Proof. By (25), we have p_{n^{2}+h} (x) = \frac{1}{x} ((x + 1)^{h}p_{n^{2}}(x) − u(n − 1)(x + 1)^{h−1}). Substituting in this equality the expression in (27) for p_{n^{2}}(x) yields the result.

Lemma 29. For n ≥ 2, we have

T_{n}(x) = ∑_{m=0}^{n^{2}−5} (∑_{k=2}^{n−1} \binom{n^{2} − k^{2} − 1}{m − k + 2}u(k − 1)) x^{m}.  (29)

Proof. From the definition and the binomial expansion, and taking into account that \binom{N}{j} = 0 if j > N (j, N ∈ ℕ), we have

T_{n}(x) = ∑_{k=2}^{n−1} u (k − 1) x^{k−2} (x + 1)^{n^{2}−k^{2}−1}

= ∑_{k=2}^{n−1} u (k − 1) x^{k−2} ∑_{j=0}^{n^{2}−k^{2}−1} \binom{n^{2} − k^{2} − 1}{j}x^{j}

= ∑_{k=2}^{n−1} u (k − 1) x^{k−2} ∑_{j≥0} \binom{n^{2} − k^{2} − 1}{j}x^{j} = ∑_{j≥0} ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} − 1}{j}u(k − 1)x^{k+j−2}

= ∑_{m≥0} ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} − 1}{m − k + 2}u(k − 1)x^{m} = ∑_{m=0}^{n^{2}−5} ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} − 1}{m − k + 2}u(k − 1)x^{m}.

Here, we have set m = k + j − 2, and we note that, for 2 ≤ k ≤ n − 1, the condition 0 ≤ m − k + 2 ≤ n^{2} − k^{2} − 1 amounts to 0 ≤ m ≤ n^{2} − k(k − 1) − 3 ≤ n^{2} − 5.

Theorem 30. For 1 ≤ h ≤ 2n + 1 and n ≥ 2, we have

u(n) =\binom{n^{2} + h − 1}{n − 1} + \binom{n^{2} + h − 2}{n − 1} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h − 1}{n − k + 1}u (k − 1)
− (h − 1) u (n − 1) .  (30)

Proof. The constant coefficient of p_{n^{2}+h}(x) = ∑_{k=n+1}^{n^{2}+h+1} v(k, n^{2} + h)x^{k−n−1} is

p_{n^{2}+h} (0) = v (n + 1, n^{2} + h) = u(n),

by (7). So u(n) is the coefficient of x^{n−1} in x^{n−1}p_{n^{2}+h} (x). Moreover by (28), we have

x^{n−1}p_{n^{2}+h} (x) = (x + 1)^{n^{2}+h−1} + (x + 1)^{n^{2}+h−2} − (x + 1)^{h} T_{n} (x) − u (n − 1) x^{n−2} (x + 1)^{h−1} ;

and, by binomial expansions, we get

(x + 1)^{h}T_{n}(x) = ∑_{k=2}^{n−1} u (k − 1) x^{k−2} (x + 1)^{n^{2}−k^{2}+h−1} =

= ∑_{k=2}^{n−1} u(k − 1) ∑_{j≥0} \binom{n^{2} − k^{2} + h − 1}{j}x^{j+k−2}.

Therefore

x^{n−1}p_{n^{2}+h} (x) = ∑_{k=0}^{n^{2}+h−1} \binom{n^{2}+h−1}{k}x^{k} + ∑_{k=0}^{n^{2}+h−2} \binom{n^{2}+h−2}{k}x^{k}

− ∑_{j≥0} ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h − 1}{j}u(k − 1)x^{j+k−2} − u (n − 1) ∑_{k=0}^{h−1} \binom{h−1}{k}x^{k+n−2}.

So the coefficient of x^{n−1} in x^{n−1}p_{n^{2}+h} (x) is the sum of the coefficients of x^{n−1} in each of the last four sums, namely

\binom{n^{2} + h − 1}{n − 1} + \binom{n^{2} + h − 2}{n − 1} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h − 1}{n − k + 1}u (k − 1) − (h − 1) u (n − 1) .

The result follows by identifying the two expressions for the coefficient of x^{n−1}.

Corollary 31. For n ≥ 2, we have

u(n) = \binom{n^{2}}{n − 1} + \binom{n^{2} − 1}{n − 1} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2}}{n − k + 1}u (k − 1) .  (31)

Proof. This is the special case h = 1 of (30).

Corollary 32. For n ≥ 2 and 0 ≤ h ≤ 2n, we have

u(n − 1) = \binom{n^{2} + h − 1}{n − 2} + \binom{n^{2} + h − 2}{n − 2} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h − 1}{n − k}u(k − 1).  (32)

Proof. Replacing h by h + 1 in (30), we get

u(n) = \binom{n^{2} + h}{n − 1} + \binom{n^{2} + h − 1}{n − 1} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h}{n − k + 1}u (k − 1) − hu (n − 1) . (33)

Then, substracting (30) from (33), and using the fundamental relation for binomial coefficients,

\binom{n}{k} − \binom{n − 1}{k} = \binom{n − 1}{k − 1},  (34)

we get the desired result.

Corollary 33. For n ≥ 3 and 0 ≤ h ≤ 2n − 1, we have

∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h − 1}{n − k − 1}u(k − 1) = \binom{n^{2} + h − 1}{n − 3} + \binom{n^{2} + h − 2}{n − 3}.  (35)

Proof. It follows from (32) that the expression

F (n, h) = \binom{n^{2} + h − 1}{n − 2} + \binom{n^{2} + h − 2}{n − 2} − ∑_{k=2}^{n−1} \binom{n^{2} − k^{2} + h − 1}{n − k}u(k − 1)

is independent of 0 ≤ h ≤ 2n. Therefore F (n, h) − F (n, h + 1) = 0 for 0 ≤ h ≤ 2n − 1, which, in view of (34), yields the desired result.

Corollary 34. For n ≥ 3 and 2 ≤ k ≤ n − 1, we have the expression in “closed form”

u(k − 1) = \frac{Δ_{n}(k)}{Δ_{n}},  (36)

where Δ_{n} is the (n − 2) × (n − 2) determinant

Δ_{n} = det ((\binom{n^{2} − k^{2} + h − 1}{n − k − 1})\begin{matrix}0≤h≤n−3 \\ 2≤k≤n−1 \end{matrix})

and Δ_{n}(k) is the determinant obtained by replacing in Δ_{n} the k-th column by the column

(\binom{n^{2} + h − 1}{n − 3} + \binom{n^{2} + h − 2}{n − 3})_{0≤h≤n−3} .

Proof. The relations (35), restricted to 0 ≤ h ≤ n−3, give a system of n−2 linear equations into the n − 2 unknowns u(1), u(2), …, u(n − 2), which can be written

∑_{k=2}^{n−1} a_{n} (k, h) u(k − 1) = b_{n}(h), 0 ≤ h ≤ n − 3,  (37)

with

a_{n}(k, h) = \binom{n^{2} − k^{2} + h − 1}{n − k − 1} and b_{n}(h) = \binom{n^{2} + h − 1}{n − 3} + \binom{n^{2} + h − 2}{n − 3}.

So, by Cramer’s rule, we get the stated expressions for u(k − 1).

Remark 35. Computations of a number of values of Δ_{n} suggested that Δ_{n} = ±1. We have since proved that Δ_{n} = (−1)^{(n−2)(n−3)/2}.

Remark 36. Computations of f(n) = log_{2} u(n) and of g(n) = \frac{f(n)}{n} for 1 ≤ n ≤ 105 seem to indicate that there exist constants 0 < c_{1} < c_{2} such that c_{1}n ≤ g(n) ≤ c_{2}n, i.e. c_{1}n^{2} ≤ f(n) ≤ c_{2}n^{2}, so that 2^{c_{1}n^{2}} ≤ u(n) ≤ 2^{c_{2}n^{2}}, for large enough n. Remark 37. The expression (37) gives another method for computing the values of u(n) quite different from the one given in (22). The two methods “fortunately” give identical numerical results. Our attempts to relate the two methods, by deducing one from the other, have so far not been fruitful. Thus the relation between the two approaches described in sections 3 and 4 remains for now an open problem. Remark 38. Here are some of the steps that led us to the polynomials p_{t} and T_{n}. We used generating functions and their ability to hold data quite tight. Set I = ℕ × ℕ and introduce the following formal series:

U(x, y) = ∑_{(n,t)∈I} u(n, t)x^{n}y^{t}, V (x, y) = ∑_{(n,t)∈I} v(n, t)x^{n}y^{t}, G(n, y) = ∑_{t≥0} u(n, t)y^{t},

and

P (x, y) = ∑_{n≥1} u(n − 1)x^{n}y^{n^{2}+1}.

Thus

U(x, y) = ∑_{n≥0} G(n, y)x^{n}.

Also, by (3)

G(n, y) = ∑_{0≤t<n^{2}} u(n, t)y^{t} + u(n)\frac{y^{n^{2}}}{1 − y} , for n ≥ 0.

In particular,

G(0, y) = ∑_{t≥0} y^{t} = \frac{1}{1 − y} .

Now, using some formulas established in section 2, we obtain relations among these generating functions. Thus, by (4) and (9), we have

V (x, 1) = ∑_{n≥0,t≥0} v(n, t)x^{n} = ∑_{t≥0} v(0, t) + ∑_{n≥1} ∑_{t=0}^{∞} v(n, t)x^{n} = ∑_{n≥1} u(n)x^{n}.

Similarly using (12), we get

(1 − y)U(x, y) = V (x, y) + 1,

and using (16), we get

(1 − y − xy)V = x − P, (1 − y)(1 − y − xy)U = 1 + x − y − xy − P.

Then, introducing F (x, y) = ∑_{t≥n−1≥0} \binom{t}{n−1}x^{n}y^{t}, we get (1 − y − xy)F = x. Hence

(1 − y − xy)(F − V) = P.

Those relations were meant to deal with the data contained in the pseudo pascalian tableau for the v(n, t)’s. To extract information from those relations, some heavy analytical machinery is probably needed.

The truncated pascalian triangle of the v(n, t)’s, given in Table 2, starts as follows (where the points represent 0’s):

The original binomial generating polynomial for the lines of Pascal’s triangle, (x + y)^{n}, had to be emulated. A glance at the tableau made it clear that only lines having a square order were needed to deal with the u(n)’s. This gave birth to the polynomials p_{t}. Starting with p_{0}(x) = v(1, 0)x = x, the first few polynomials are easy to obtain, by induction:

p_{1}(x) = ((1 + x)x − 0)/x = 1 + x,
p_{2}(x) = ((1 + x)(1 + x) − 1)/x = 2 + x,
p_{3}(x) = (2 + x)(1 + x) = 2 + 3x + x^{2},
p_{4}(x) = (2 + x)(1 + x)^{2} = 2 + 5x + 4x^{2} + x^{3},
p_{5}(x) = ((2 + x)(1 + x)^{3} − 2)/x = 7 + 9x + 5x^{2} + x^{4}.

t/n 1 2 3 4 5 6 7
0 1
1 1 1
2 · 2 1
3 · 2 3 1
4 · 2 5 4 1
5 · · 7 9 5 1
6 · · 7 16 14 6 1
7 · · 7 23 30 20 7
8 · · 7 30 53 50 27
9 · · 7 37 83 103 77
10 ⋯ 44 120
11 ⋯ 44 164
12 ⋯ 44 208
13 ⋯ 44 252
14 ⋯ 44 296
15 ⋯ 44 340
16 ⋯ 44 384
17 ⋯ 428
18 ⋯ 428

Table 2: Truncated pascalian table

A look at the list strongly suggested the introduction of the T_{n}’s. That is about everything.

5 Acknowledgment

We would like to expressly thank the referee who made a careful reading of our article, asked pertinent questions, and made relevant suggestions that we fully took into account. This helped improve the original version of the article and enrich its contents.

References

[1] P. Erdős and W. H. J. Fuchs, On a problem of additive number theory, J. London Math. Soc. 31 (1956), 67–73.

[2] P. Erdős and P. Turán, On a problem of Sidon in additive number theory, J. London Math. Soc. 16 (1941), 212–215.

[3] G. Grekos, L. Haddad, C. Helou, and J. Pihko, The class of Erdős-Turán sets, Acta Arith. 117 (2005), 81–105.

[4] G. Grekos, L. Haddad, C. Helou, and J. Pihko, On the general Erdős-Turán conjecture, Int. J. Comb. (2014), Article ID 826141.

[5] H. Halberstam and K. F. Roth, Sequences, Oxford Clarendon Press, 1966.

[6] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 05A15, 05A19, 11B65, 11B75. Keywords: finite sequence, binomial coefficient, combinatorics, enumeration.

(Concerned with sequence \underline{A242105}.)

Received August 24 2014; revised versions received September 2 2014; January 12 2015. Published in Journal of Integer Sequences, January 13 2015.

Return to Journal of Integer Sequences home page.