\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Finite Sequences Dominated by the Squares 
}
\vskip 1cm
\large
L. Haddad \\
120 rue de Charonne \\
75011 Paris \\
France  \\
\href{mailto:labib.haddad@wanadoo.fr}{\tt labib.haddad@wanadoo.fr} \\
\ \\
C. Helou \\
Department of Mathematics \\
Pennsylvania State University \\
25 Yearsley Mill Road \\
Media, PA 19063 \\
USA \\
\href{mailto:cxh22@psu.edu}{\tt cxh22@psu.edu}\\
\end{center}

\vskip .2 in

%\newcommand{\df}{\dfrac}
%\renewcommand{\i}{\infty}
%\renewcommand{\a}{\alpha}

%\setbox0=\hbox{$+$}
%\newdimen\plusheight
%\plusheight=\ht0
%\def\+{\;\lower\plusheight\hbox{$+$}\;}

%\setbox0=\hbox{$-$}
%\newdimen\minusheight
%\minusheight=\ht0
%\def\-{\;\lower\minusheight\hbox{$-$}\;}

%\setbox0=\hbox{$\cdots$}
%\newdimen\cdotsheight
%\cdotsheight=\plusheight%\ht0
%\def\cds{\lower\cdotsheight\hbox{$\cdots$}}


\begin{abstract}
We evaluate the number $u(n)$ of length-$n$
finite sequences $(a_k)_{1\leq k \leq n}$ of
natural numbers that satisfy the
inequality $a_k \leq 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.
\end{abstract}


\section{Introduction} 
\label{sec: Intro}

The general Erd\H{o}s-Tur\'{a}n conjecture(\cite {E-T, E-F, H-R}) states that if $A=\{a_{1}<a_{2}<\cdots <a_{n}<\cdots  \}$ is an infinite subset 
of the set $\mathbb{N} =\{0,1,2,3\ldots \}$ of natural numbers satisfying $a_n \leq cn^2$ for all integers $n\geq 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) \in A\times A : a_i +a_j =n \}|$, for $n \in \mathbb{N}$, 
is unbounded. In a previous paper (\cite {CET}), we established that it is enough to prove the conjecture for sequences satisfying $a_n \leq n^2$ for all $n\geq 1$. 
More recently, we undertook a quantitative exploration of the conjecture (\cite {GET}) by studying a 
function $\psi (n)$ defined on the set $\mathcal A (n)$ of all sequences $A=\{a_{1}<a_{2}<\cdots <a_{n}\}$ of $n$ elements in $\mathbb{N}$ 
dominated by the squares, i.e., satisfying $a_{k}\leq k^{2}$ for $1\leq k\leq n$. In the process, a natural question that came up was the determination of the number 
$u(n) = \left\vert \mathcal A(n) \right\vert $ 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\left( n,t\right) =\left\vert \mathcal A(n,t)\right\vert $ and 
$v\left( n,t\right) =\left\vert \mathcal A(n|t)\right\vert$, depending on two integer
parameters $n,t\in \mathbb{N}$, in terms of which $u(n)$ can be simply expressed, where $\mathcal A(n,t)$
(resp. $\mathcal A(n|t))$ is the set of all subsets of $\mathcal A(n)$
contained in the interval $\left[ 0,t\right] $ (resp. whose largest element 
$a_{n}=t)$. We thus prove (\eqref{9} and \eqref{11}) that
$$u(n)=\sum\limits_{t=n-1}^{n^{2}}v(n,t)=u(n,n^{2}-k)+k\cdot u(n-1),\quad \text {for} \quad n\geq 1, \ 1\leq k\leq 2n-1.$$

These double sequences $\left( u(n,t)\right) _{n,t}$ and $\left( v\left(n,t\right) \right) _{n,t}$ 
have properties of intrinsic interest. For instance, they satisfy the relations (\eqref{14} and \eqref{16} )
$$u(n,t)=u(n,t-1)+u(n-1,t-1), \quad v(n,t)=v(n,t-1)+v(n-1,t-1), \quad \text {for} \ 1\leq t\leq n^{2}.$$
These relations are similar to the ones satisfied by the binomial
coefficients, but they are subject to the restriction $t\leq 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 (\eqref{22} and \eqref{32}), for $n \geq 2$,  
$$u(n) =\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{\left( n-k+1\right)^{2} +k-1}{k}u(n-k);$$ 
and
$$u(n)=\binom{n^{2}}{n-1}+\binom{n^{2}-1}{n-1}-\sum\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}}{n-k+1}u\left( k-1\right).$$ 
We also establish an explicit expression in ``closed form'' for $u(n)$, namely (\eqref{37})
$$u(k-1)=\frac{\Delta _{n}(k)}{\Delta _{n}},\quad \text {for} \ 2\leq k\leq n-1,$$
where $\Delta _{n}$ is the $\left( n-2\right) \times \left( n-2\right)$ determinant 
$$\Delta _{n}=\det \left( \left( a_{n}(h,k)\right) _{\substack{0\leq h\leq n-3  \\ 2\leq k\leq n-1}}\right),$$ 
and $\Delta _{n}(k)$ is the determinant obtained by replacing in $\Delta _{n}$ the $k$-th column by the
column $\left( b_{n}(h)\right) _{0\leq h\leq n-3}$, with 
$$a_{n}(h,k)= \binom{n^{2}-k^{2}+h-1}{n-k-1}, \quad \text {and} \quad b_{n}(h)=\binom{n^{2}+h-1}{n-3}+\binom{n^{2}+h-2}{n-3}, $$
for $0\leq h\leq n-3$ and $2\leq k\leq n-1$. However this expression is not practical, since the size of the determinant grows with $n$.

The sequence $(u(n))_{n\in \mathbb{N}}$ appears in N. J. A. Sloane's database,
\it The On-line Encyclopedia of Integer Sequences \rm (OEIS) \cite{OEIS},
as \seqnum{A242105}.



\section{The auxiliary double sequences} \label{auxiliary}

For any $n\in \mathbb{N}$, let $\mathcal A(n)$ be the set of all subsets $A=\{a_{1}<a_{2}<\cdots <a_{n}\}$ 
of $\mathbb{N}$ of cardinality $\left\vert A\right\vert =n$, satisfying $a_{k}\leq k^{2}$
for $1\leq k\leq n$. Also, for any $n,t\in \mathbb{N}$, let 
$$\mathcal A(n,t)=\left\{ A\in \mathcal A(n):A\subset \lbrack 0,t]\right\},$$
and 
$$ \mathcal A(n|t)=\left\{ A\in \mathcal A(n):\max \left( A\right) =t\right\}.$$
Further, let $u\left( n\right) =\left\vert \mathcal A\left( n\right) \right\vert$ , 
$u\left( n,t\right) =\left\vert \mathcal A(n,t)\right\vert$, and  $v\left( n,t\right) =\left\vert \mathcal A (n|t)\right\vert .$

Obviously, 
\begin {equation}\label{1} 
  u(0)=1, \qquad u(1)=2.
\end {equation}
It follows from the definitions that if $n>0$ and $A=\{a_{1}< \cdots <a_{n}\}\in \mathcal A(n)$, then
\begin {equation}\label{2}
k-1\leq a_{k}\leq k^{2},\quad \text {for $1\leq k\leq n$}.
\end{equation}
It is not difficult to see that 
\begin {equation}\label{3}
u(n,t) = \begin{cases}
0, & \text{ if  $0\leq t<n-1$}; \\ 
1, & \text{ if $n=0$  or $(n=1,t=0)$}; \\ 
u(n), & \text{ if $t\geq n^{2}\geq 1$}.
\end{cases}
\end{equation}
Also, 
\begin {equation}\label{4}
v(n,t)= \begin{cases}
0, & \text{ if $n=0$ or  $(t=0, n\neq 1)$ or $t<n-1$ or $t>n^2$}; \\ 
1, & \text{ if $n=1$ and $t=0, 1$}.
\end{cases}
\end {equation}
Moreover, 
\begin {equation}\label{5}
u(n,n-1)=v\left( n,n-1\right) =1, \quad \text {for $n\geq 1$}.
\end {equation}

\begin{lemma}\label{Lem1} 
For $n,t\in \mathbb {N}$, we have
\begin {equation}\label{6}
v(n,t)= \begin{cases}
u(n-1, t-1), & \text{ if  $t\leq n^{2}$}; \\ 
0, & \text{ if $t>n^{2}$ }. 
\end{cases}
\end {equation}
\end{lemma}
\begin{proof}
If $t\leq n^{2}$, then $\mathcal A(n|t)=\{A\cup \{t\}:A\in \mathcal A(n-1,t-1)\}$, and therefore 
$v(n,t)= u\left( n-1,t-1\right)$. For $t>n^{2}$, the result follows from \eqref{4}.
\end{proof}

\begin{remark}\label{Rem1} It follows from \eqref{6} and \eqref{3} that
\begin {equation}\label{7}
v(n,t)=u\left( n-1,t-1\right) =u\left( n-1\right),\quad \text {for $\left( n-1\right)^{2}<t\leq n^{2}$}.
\end{equation}
Therefore
\begin {equation}\label{8}
u(n)=v\left( n+1,t\right),\quad \text {for $n^{2}<t\leq (n+1)^{2}$}.
\end {equation}
\end{remark}

\begin{lemma}\label{Lem2} For $n\geq 1$, we have
\begin {equation}\label{9}
u(n)=\sum\limits_{t=n-1}^{n^{2}}v(n,t) = \sum\limits_{t=0}^{\infty}v(n,t).
\end{equation}
\end{lemma}
\begin{proof} It follows from \eqref{2} that 
$\mathcal A(n)=\bigcup\limits_{t=n-1}^{n^{2}}\mathcal A(n|t)$, a union of pairwise disjoint sets. Hence the first equality. The second equality follows from \eqref{4}. 
\end{proof}

\begin{lemma}\label{Lem3} For any $n,s,t\in \mathbb{N}$ such that $s<t$, we have
\begin {equation}\label{10}
u(n,t)=u(n,s)+\sum\limits_{k=s+1}^{t}v(n,k). 
\end{equation}
\end{lemma}
\begin{proof} This follows from the simple equality 
$\mathcal A(n,t)=\mathcal A(n,s)\bigcup \left( \bigcup\limits_{k=s+1}^{t} \mathcal A(n|k)\right)$, 
with a union of pairwise disjoint sets. 
\end{proof}

\begin{lemma}\label{Lem4} For $n\geq 1$ and $1\leq k\leq 2n-1$, we have
\begin {equation}\label{11}
u(n)=u(n,n^{2}-k)+k\cdot u(n-1).
\end{equation}
\end{lemma}
\begin{proof}
By \eqref{3} and \eqref{10}, we have 
$$u(n)=u(n,n^{2})=u(n,n^{2}-k)+\sum\limits_{j=n^{2}-k+1}^{n^{2}}v(n,j).$$
Moreover, for $1\leq k\leq 2n-1$ and $n^{2}-k<j\leq n^{2}$, we have $\left( n-1\right)^{2} <j\leq n^{2}$, and therefore   
$v(n,j)=u(n-1)$, by \eqref{7}. Hence the result.
\end{proof}

\begin{remark}\label{Rem2} It follows from \eqref{10} with $s=t-1$, that, for $n\geq 0, t\geq 1$, we have
\begin {equation}\label{12}
u(n,t)=u\left( n,t-1\right) +v\left( n,t\right).
\end{equation}
\end{remark} 

\begin{lemma}\label{Cor1} For $1\leq t\leq n^{2}$, we have 
\begin {equation}\label{14}
u(n,t)=u(n,t-1)+u(n-1,t-1).
\end{equation}
\end{lemma}
\begin{proof} 
We clearly have 
$$\mathcal A(n,t) = \mathcal A(n|t) \cup \mathcal A(n,t-1),$$
and 
$$\mathcal A(n|t) \cap \mathcal A(n,t-1) =\emptyset.$$
Hence 
$$u(n,t)= \vert \mathcal A(n,t) \vert = \vert \mathcal A(n|t) \vert +  \vert \mathcal A(n,t-1) \vert = v(n,t) + u(n, t-1).$$
Moreover, by \eqref{6}, 
$$v(n,t) = u(n-1, t-1).$$
The result follows immediately.
\end{proof}



\begin{lemma}\label{Cor2} For $1\leq t\leq n^{2}$, we have
\begin {equation}\label{16}
v(n,t)=v(n,t-1)+v(n-1,t-1).
\end{equation}
\end{lemma}
\begin{proof}
It can be easily verified that the relation holds for $t=1$. So we may assume that $2 \leq t \leq n^2$.
We have a bijection 
$$f: \mathcal A(n|t) \to \mathcal A(n-1|t-1) \cup \mathcal A(n-1, t-2)$$ 
which, to $A=\{a_{1}<a_{2}<\cdots <a_{n}\}$, with $a_n =t$, makes correspond 
$$f(A) = A \setminus \{ t \} = \{a_{1}<a_{2}<\cdots <a_{n-1}\}$$.  
And we have   
$$\mathcal A(n-1|t-1) \cap \mathcal A(n-1, t-2) = \emptyset.$$
Hence
$$v(n,t) = \vert \mathcal A(n|t) \vert = \vert \mathcal A(n-1|t-1) \vert + \vert \mathcal A(n-1, t-2) \vert  
=v(n-1, t-1) + u(n-1, t-2).$$ 
Moreover, by \eqref{6}, $v(n, t-1) = u(n-1, t-2)$. 
The result follows immediately.
\end{proof}

\begin{lemma}\label{Lem5} For $n,t\geq 1$, we have 
\begin {equation}\label{13}
u(n,t)-u(n,t-1)= \begin{cases}
u(n-1,t-1), & \text{if $t\leq n^{2}$}; \\ 
0, & \text{if $t>n^{2}$}.
\end{cases}
\end{equation}
\end{lemma}
\begin{proof}
By \eqref{12}, we have $u(n,t)-u\left( n,t-1\right) =v\left( n,t\right)$, and the result follows from \eqref{6}. 
\end{proof}

\begin{lemma}\label{Lem6} For $n,t\geq 1$, we have 
\begin {equation}\label{15}
v(n,t)-v(n,t-1)-v\left( n-1,t-1\right) = \begin{cases}
-u(n-1), & \text{if $t=n^{2}+1$}; \\ 
0 & \text{{if $t \neq n^{2}+1$}}. 
\end{cases}
\end{equation}
\end{lemma}
\begin{proof}
If $t=n^{2}+1$, then, by \eqref{4} and \eqref{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 \eqref{4}, all terms on the left are $=0$ and the last case holds.

If $1\leq t\leq n^{2}$, then, by \eqref{6}, $v(n,t)=u(n-1,t-1)$ and $v(n,t-1)=u\left( n-1,t-2\right)$;  
and, by \eqref{12}, $v\left( n-1,t-1\right) = u(n-1,t-1)-u(n-1,t-2)$. Therefore 
$$v(n,t)-v(n,t-1)-v\left( n-1,t-1\right) = 0.$$
Hence the result.  
\end{proof}



\begin{example}\label{Ex1} Using the relation \eqref{16}, 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{center}
$\begin{array}{cccccccccccc}
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{array}$
\end{center}
\end{example}

\begin{proposition}\label{Prop1} For $k,n,t\in \mathbb{N}$ such that $1\leq k\leq n$ and $k\leq t\leq \left( n-k+1\right) ^{2}+k-1$, we have
\begin {equation}\label{17}
u(n,t)=\sum\limits_{i=0}^{k}\binom {k}{i}u(n-i,t-k).
\end{equation}
\end{proposition}
\begin{proof}
For a given $n\geq 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\leq t\leq n^{2}$, by \eqref{14}.

Assume the equality holds for some $1\leq k<n$ and all $k\leq t\leq \left( n-k+1\right) ^{2}+k-1$. 
Then, for $k+1 \leq t \leq (n-k)^2 +k$, we have, by \eqref{14}, 
$$u(n-i,t-k)=u(n-i,t-k-1)+u(n-i-1,t-k-1),$$ 
for $0\leq i\leq k$. Hence 
\begin{align}
u(n,t)&= \sum\limits_{i=0}^{k}\binom{k}{i}u(n-i,t-k)=\sum\limits_{i=0}^{k} \binom{k}{i}\left( u(n-i,t-k-1)+u(n-i-1,t-k-1)\right) =    \notag \\  
& = \sum\limits_{i=0}^{k}\binom{k}{i}u(n-i,t-k-1)+\sum\limits_{j=1}^{k+1} \binom{k}{j-1}u(n-j,t-k-1)=    \notag \\  
& = \sum\limits_{i=1}^{k}\left( \binom{k}{i}+\binom{k}{i-1} \right) u(n-i,t-k-1) + \notag \\
& +u(n,t-k-1)+ u(n-k-1,t-k-1)    \notag \\  
& = \sum\limits_{i=0}^{k+1}\binom{k+1}{i}u(n-i,t-\left( k+1\right) ),\quad \text {for} \ k+1\leq t\leq \left( n-k\right) ^{2}+k.   \notag 
\end{align}
So the equality holds for $k+1$ and all $k+1 \leq t \leq (n-k)^2 +k$. This completes the induction. 
\end{proof}


\section{The main sequence $\left( u\left( n\right) \right)_{n\geq 0}$}\label{Main}

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.

\begin{lemma}\label{Lem7} For all integers $N\geq m\geq 0$, we have
\begin {equation}\label{18}
\sum\limits_{k=m}^{N}\binom{k}{m}=\binom{N+1}{m+1}.
\end{equation}
\end{lemma}
\begin{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}.$$
\end{proof}

\begin{corollary}\label{Cor3} For all integers $N \geq M \geq m\geq 0$, we have
\begin {equation}\label{19}
\sum\limits_{k=M}^{N}\binom{k}{m}=\sum
\limits_{k=m}^{N}\binom{k}{m}-\sum\limits_{k=m}^{M-1}\binom{k}{m}=
\binom{N+1}{m+1}-\binom{M}{m+1}.
\end{equation}
\end{corollary}

\begin{remark}\label{Rem3}
In the remainder of this section, we set $a_{0} =0$.
\end{remark}

\begin{lemma}\label{Lem8} For $n\geq 1$, we have
\begin {equation}\label{20}
u\left( n\right) =\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n}=a_{n-1}+1}^{n^{2}}1.
\end{equation}
\end{lemma}
\begin{proof}
By definition, $\mathcal A(n)$ consists of all subsets $A=\{a_{1}<a_{2}<\cdots <a_{n}\}$ of $\mathbb{N}$ satisfying
$$0\leq a_{1}\leq 1, \  a_{1}+1 \leq a_{2}\leq 4, \ a_{2}+1 \leq a_{3}\leq 9, \dots , a_{n-1}+1 \leq a_{n}\leq n^{2}.$$
The stated relation for $u\left( n\right) =\left\vert \mathcal A\left( n\right)\right\vert$ follows immediately.
\end{proof}

\begin{theorem}\label{Th1} For $n\geq 2$ and $1\leq h\leq n-1$, we have
\begin{align}\label{21}
u(n) & =\sum\limits_{k=1}^{h}(-1)^{k-1}\binom{\left( n-k+1\right)^{2}+k-1}{k}u(n-k)+  \notag \\  
&  +\left( -1\right)^{h}\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h}=a_{n-h-1}+1}^{(n-h)^{2}}\binom{a_{n-h}+h-1}{h}. 
\end{align}
\end{theorem}
\begin{proof}
For a fixed $n\geq 2$, the proof is by induction on $h$. 

First, note that the truth of \eqref{21} for $h=1$ follows immediately from \eqref{20}

Assume now, by induction, that \eqref{21} holds for some $1\leq h<n-1$. By \eqref{19}, we have 
\begin{align}
\sum\limits_{a_{n-h}=a_{n-h-1}+1}^{(n-h)^{2}}\binom{a_{n-h}+h-1}{h}=\sum\limits_{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}, \notag
\end{align}
and substituting this into (21) yields  
\begin{align}
u(n) & =\sum\limits_{k=1}^{h}(-1)^{k-1}\binom{\left( n-k+1\right) ^{2}+k-1}{k}u(n-k)+ \notag \\
& +\left( -1\right)^{h}\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h-1}=a_{n-h-2}+1}^{(n-h-1)^{2}}\left( \binom{(n-h)^{2}+h}{h+1}-\binom{a_{n-h-1}+h}{h+1}\right) = \notag \\
& =\sum\limits_{k=1}^{h}(-1)^{k-1}\binom{\left( n-k+1\right) ^{2}+k-1}{k}u(n-k)+ \notag \\
& +\left( -1\right) ^{h}\binom{(n-h)^{2}+h}{h+1}\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h-1}=a_{n-h-2}+1}^{(n-h-1)^{2}} 1+ \notag \\ 
& +\left( -1\right)^{h+1}\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h-1}=a_{n-h-2}+1}^{(n-h-1)^{2}}\binom{a_{n-h-1}+h}{h+1}. \notag 
\end{align}
Moreover, by \eqref{20},
\begin{align}
\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h-1}=a_{n-h-2}+1}^{(n-h-1)^{2}} 1 = u(n-h-1). \notag
\end{align}
Hence
\begin{align} 
u(n) & =\sum\limits_{k=1}^{h}(-1)^{k-1}\binom{\left( n-k+1\right) ^{2}+k-1}{k}
u(n-k)+\left( -1\right) ^{h}\binom{(n-h)^{2}+h}{h+1}u(n-h-1)+ \notag \\
&  +\left( -1\right)^{h+1}\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h-1}=a_{n-h-2}+1}^{(n-h-1)^{2}}\binom{a_{n-h-1}+h}{h+1}= \notag \\
& =\sum\limits_{k=1}^{h+1}(-1)^{k-1}\binom{\left( n-k+1\right) ^{2}+k-1}{k}u(n-k)+ \notag \\
& \left( -1\right)^{h+1}\sum\limits_{a_{1}=0}^{1}\sum\limits_{a_{2}=a_{1}+1}^{4}\cdots
\sum\limits_{a_{n-h-1}=a_{n-h-2}+1}^{(n-h-1)^{2}}\binom{a_{n-h-1}+h}{h+1}, \notag
\end{align}
which is just the expression \eqref{21} for $h+1$ replacing $h$. This completes the proof by induction of \eqref{21}.
\end{proof}

\begin{corollary}\label{Cor4}  For $n\geq 2$, we have
\begin {equation}\label{22}
u(n)=\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{\left( n-k+1\right)^{2}+k-1}{k}u(n-k).
\end{equation}
\end{corollary}
\begin{proof}
Taking $h=n-1$, the multiple sum in \eqref{21} reduces to  
$$(-1)^{n-1}\sum\limits_{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)$.
\end{proof}

\begin{example}\label{Ex2}  Using \eqref{22} and \eqref{1}, we can compute $u(n)$ recursively. We thus obtain the data in Table~\ref{tab1}.
\begin{table}
\begin{center}
\begin{tabular}{l|r}
$n$ & $u(n)$ \\
\hline
0 & 1 \\
1 & 2 \\
2 & 7 \\
3 & 44 \\
4 & 428 \\
5 & 5802 \\
6 & 102322 \\
7 & 2239844 \\
8 & 58849332 \\
9 & 1810039960 \\
10 & 63930543419 \\
\end{tabular}
\end{center}
\caption{First few values of $u(n)$}
\label{tab1}
\end{table}

More values of $u(n)$ can be found in
\seqnum{A242105} of the OEIS (\cite{OEIS}).
\end{example} 


\section{An alternative approach}\label{Alternative}


\begin{definition}\label{Def1}
For $t\in \mathbb{N}$, let $t^{\ast }=\left\lceil \sqrt{t}\right\rceil $ be the least integer $\geq \sqrt{t}$, so that 
$t^{\ast }=m$ if and only if $\left( m-1\right)^{2}<t\leq m^{2}$ for some $m\in \mathbb{N}$, and let
\begin {equation}\label{23}
 p_{t}(x)= \sum\limits_{n=t^{\ast }}^{t+1}v(n,t)x^{n-t^{\ast }}=x^{t+1-t^{\ast
}}+\sum\limits_{n=t^{\ast }}^{t}v(n,t)x^{n-t^{\ast }}.
\end{equation}
\end{definition}

\begin{proposition}\label{Prop2} For $t \geq 1$, the polynomials $p_{t}$ satisfy the following
recurrence formula.
\begin{equation}\label{24}
p_{t+1}(x)= \begin{cases}
\dfrac{1}{x}\left( \left( x+1\right) p_{t}(x)-u\left( m-1\right) \right), 
& \text{ if $t=m^{2}$, with $m\in \mathbb{N}$}; \\ 
\left( x+1\right) p_{t}(x), & \text{ otherwise}.
\end{cases}
\end{equation}
\end{proposition}
\begin{proof}
Note first that if  $n\geq (t+1)^{\ast }$ then $n^2 >t$, and that by \eqref{16}, $v\left( n,t+1 \right) =v(n,t)+v(n-1,t)$, for$\ 0\leq t<n^{2}$.
Hence 
\begin{align}
p_{t+1}(x) & = \sum\limits_{n=(t+1)^{\ast}}^{t+2}v(n,t+1)x^{n-(t+1)^{\ast }}=
\sum\limits_{n=(t+1)^{\ast}}^{t+2}\left( v(n,t)+v(n-1,t)\right) x^{n-(t+1)^{\ast }}= \notag \\
& = \sum\limits_{n=(t+1)^{\ast }}^{t+2}v(n,t)x^{n-(t+1)^{\ast}}+\sum\limits_{n=(t+1)^{\ast }-1}^{t+1}v(n,t)x^{n+1-(t+1)^{\ast }}. \notag
\end{align}
If $t=m^{2}$, then $t^{\ast }=m$ and $\left( t+1\right) ^{\ast }=m+1$, so that
\begin{align}
& \sum\limits_{n=(t+1)^{\ast }}^{t+2}v(n,t)x^{n-(t+1)^{\ast}}=
\sum\limits_{n=m+1}^{m^{2}+2}v(n,m^{2})x^{n-m-1}=\dfrac{1}{x}
\sum\limits_{n=t^{\ast }+1}^{t+2}v(n,t)x^{n-t^{\ast }}= \notag \\
& =\dfrac{1}{x}\left( p_{t}(x)-v\left( m,m^{2}\right) +v\left(
m^{2}+2,m^{2}\right) x^{m^{2}+2-m}\right) =\dfrac{1}{x}\left( p_{t}(x)-u\left( m-1\right) \right), \notag
\end{align}
since $v\left( m,m^{2}\right) =u(m-1)$ by \eqref{8}, and $v\left(m^{2}+2,m^{2}\right) =0$ by \eqref{4}, and 
$$\sum\limits_{n=(t+1)^{\ast }-1}^{t+1}v(n,t)x^{n+1-(t+1)^{\ast}}=\sum\limits_{n=m}^{m^{2}+1}v(n,m^{2})x^{n-m}=
\sum\limits_{n=t^{\ast}}^{t+1}v(n,t)x^{n-t^{\ast }}=p_{t}(x).$$
Therefore, in the case $t=m^{2}$, we have
$$p_{t+1}(x)= \dfrac{1}{x}\left( p_{t}(x)-u\left( m-1\right) \right) +p_{t}(x)= \dfrac{1}{x}\left( \left( x+1\right) p_{t}(x)
-u\left( m-1\right) \right).$$

Otherwise, if $t$ is not a square, i.e., $m^{2}<t<\left( m+1\right) ^{2}$, 
with $m\in \mathbb{N}$, then $t^{\ast }=\left( t+1\right) ^{\ast }=m+1$, so that
$$\sum\limits_{n=(t+1)^{\ast }}^{t+2}v(n,t)x^{n-(t+1)^{\ast}}=\sum\limits_{n=t^{\ast }}^{t+2}v(n,t)x^{n-t^{\ast }} = 
p_{t}(x)+v\left( t+2,t\right) x^{t+2-t^{\ast }}=p_{t}(x),$$
since $v\left( t+2,t\right) =0$ by \eqref{4}; and  
\begin{align}
\sum\limits_{n=(t+1)^{\ast}-1}^{t+1}v(n,t)x^{n+1-(t+1)^{\ast }} & =
\sum\limits_{n=t^{\ast}-1}^{t+1}v(n,t)x^{n+1-t^{\ast }}=x\sum\limits_{n=t^{\ast
}-1}^{t+1}v(n,t)x^{n-t^{\ast }} = \notag \\
& = x\left( p_{t}(x)+v\left( t^{\ast}-1,t\right) x^{-1}\right) =xp_{t}\left( x\right), \notag 
\end{align}
since $v\left( t^{\ast }-1,t\right) =v\left( m,t\right) =0$, by \eqref{4}. Therefore, in this case, we have
$$p_{t+1}(x)= p_{t}(x)+xp_{t}(x)=\left( x+1\right) p_{t}(x).$$ 
\end{proof}

\begin{corollary}\label{Cor5} For $n \geq 1$ and $1\leq h\leq 2n+1$, we have
\begin{equation}\label{25}
p_{n^{2}+h}\left( x\right) =\dfrac{1}{x}\left( \left( x+1\right)
^{h}p_{n^{2}}(x)-u\left( n-1\right) \left( x+1\right) ^{h-1}\right).
\end{equation}
\end{corollary}
\begin{proof} The proof is by induction on $h$.
By \eqref{24}, $\ p_{n^{2}+1}\left( x\right) =\dfrac{1}{x}\left( \left( x+1\right)
p_{n^{2}}(x)-u\left( n-1\right) \right)$, so that the property holds for $h=1$. 
Assume, by induction that it holds for some $1\leq h\leq 2n$. Then, by \eqref{24} and the induction assumption,
\begin{align}
p_{n^{2}+h+1}\left( x\right) & = \left( x+1\right) p_{n^{2}+h}\left( x\right) =
\dfrac{x+1}{x}\left( \left( x+1\right) ^{h}p_{n^{2}}(x)-u\left( n-1\right)
\left( x+1\right) ^{h-1}\right) = \notag \\
&  =\dfrac{1}{x}\left( \left( x+1\right)
^{h+1}p_{n^{2}}(x)-u\left( n-1\right) \left( x+1\right) ^{h}\right), \notag 
\end{align}
which shows that the result holds for $h+1$ and completes the induction.
\end{proof}

\begin{example}\label{Ex3} We have 
$$p_{0}(x)=x,\qquad p_{1}(x)=x+1, \qquad p_{2}(x)=x+2,$$ 
$$p_{3}(x)=x^{2}+3x+2,  \qquad p_{4}(x)=x^{3}+4x^{2}+5x+2, \qquad p_{5}(x)=x^{3}+5x^{2}+9x+7.$$
\end{example}

\begin{definition}\label{Def2} For any integer $n\geq 2$, let 
$$T_{n}(x)=\sum \limits_{k=2}^{n-1}u\left( k-1\right) x^{k-2}\left( x+1\right)^{n^{2}-k^{2}-1}.$$
\end{definition}

\begin{example}\label{Ex4} We have 
$$T_{2}\left( x\right) =0, \quad T_{3}\left( x\right) =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.$$
\end{example}

\begin{lemma}\label{Lem9} For $n\geq 2$, we have
\begin{equation}\label{26}
T_{n+1}(x)=\left( x+1\right) ^{2n+1}T_{n}\left( x\right)
+u\left( n-1\right) x^{n-2}\left( x+1\right) ^{2n}.
\end{equation}
\end{lemma}
\begin{proof} \ By definition, 
\begin{align}
T_{n+1}(x) & = \sum\limits_{k=2}^{n}u\left( k-1\right) x^{k-2}\left( x+1\right)^{(n+1)^{2}-k^{2}-1}
=\sum\limits_{k=2}^{n}u\left( k-1\right) x^{k-2}\left( x+1\right) ^{n^{2}+2n-k^{2}} \notag \\
& =\left( x+1\right) ^{2n+1}\sum\limits_{k=2}^{n-1}u\left( k-1\right)
x^{k-2}\left( x+1\right) ^{n^{2}-k^{2}-1}+u(n-1)x^{n-2}\left( x+1\right)^{2n}= \notag \\
&  =\left( x+1\right) ^{2n+1}T_{n}\left( x\right) +u\left( n-1\right)
x^{n-2}\left( x+1\right) ^{2n}. \notag
\end{align}
\end{proof}

\begin{lemma}\label{Lem10} For $n\geq 2$, we have
\begin{equation}\label{27}
p_{n^{2}}\left( x\right) =\dfrac{\left( x+1\right)^{n^{2}-1}+\left( x+1\right) ^{n^{2}-2}-T_{n}(x)}{x^{n-2}}.
\end{equation}
\end{lemma}
\begin{proof} The proof is by induction on $n$.
Using the Examples given above, it is easily verified that 
$p_{4}(x)=\left( x+1\right) ^{3}+\left( x+1\right) ^{2}-T_{2}\left( x\right)$,  
so that the relation holds for $n=2$.

Assume inductively that it holds for $n$. Then, by \eqref{25}, the induction assumption and \eqref{26}, we have 
\begin{align}
x p_{(n+1)^{2}}(x) & = xp_{n^{2}+2n+1}\left( x\right) =  \left( x+1\right)
^{2n+1}p_{n^{2}}(x)-u\left( n-1\right) \left( x+1\right) ^{2n} = \notag \\
& = \left( x+1\right) ^{2n+1}\frac{\left( x+1\right)^{n^{2}-1}
+\left( x+1\right) ^{n^{2}-2}-T_{n}(x)}{x^{n-2}}-u\left( n-1\right) \left( x+1\right) ^{2n}.  \notag 
\end{align}
Therefore
\begin{align}
x^{n-1} p_{(n+1)^{2}}(x)  = & \left( x+1\right) ^{n^{2}+2n}+\left( x+1\right)^{n^{2}+2n-1} 
-\left( x+1\right) ^{2n+1}T_{n}(x) \notag \\ 
& - u\left( n-1\right) x^{n-2}\left( x+1\right) ^{2n} = \left( x+1\right) ^{(n+1)^{2}-1}+\left( x+1\right)^{(n+1)^{2}-2}-T_{n+1}(x). \notag 
\end{align}
Thus the relation holds for $n+1$. 
\end{proof}

\begin{corollary}\label{Cor6} For  $n\geq 2$ and $1\leq h\leq 2n+1$, we have
\begin{align}\label{28}
p_{n^{2}+h}(x) & =  \\
& = \frac{\left( x+1\right) ^{n^{2}+h-1}+\left( x+1\right) ^{n^{2}+h-2}-\left( x+1\right)^{h} 
T_{n}\left( x\right) -u\left( n-1\right) x^{n-2}\left( x+1\right) ^{h-1}}{x^{n-1}}. \notag
\end{align}
\end{corollary}
\begin{proof}
By \eqref{25}, we have 
$p_{n^{2}+h}\left( x\right)  = \frac 1x \left( (x+1)^h p_{n^{2}}(x)-u( n-1) (x+1)^{h-1} \right)$. 
Substituting in this equality the expression in \eqref{27} for $p_{n^2}(x)$ yields the result.
\end{proof}

\begin{lemma}\label{Lem11} For $n\geq 2$, we have 
\begin{equation}\label{29}
T_{n}(x) = \sum\limits_{m=0}^{n^{2}-5}\left( \sum\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}-1}{m-k+2}u(k-1)\right) x^{m}.
\end{equation}
\end{lemma}
\begin{proof} From the definition and the binomial expansion, and taking into account that $\binom Nj =0$ if $j>N$ ($j, N \in \mathbb N$), we have 
\begin{align}
T_{n}(x) & = \sum\limits_{k=2}^{n-1}u\left( k-1\right) x^{k-2}\left( x+1\right) ^{n^{2}-k^{2}-1} \notag \\
& = \sum\limits_{k=2}^{n-1}u\left( k-1\right) x^{k-2}\sum\limits_{j=0}^{n^{2}-k^{2}-1}\binom{n^{2}-k^{2}-1}{j}x^{j} \notag \\
& = \sum\limits_{k=2}^{n-1}u\left( k-1\right) x^{k-2}\sum\limits_{j \geq 0} \binom{n^{2}-k^{2}-1}{j}x^{j} =  
\sum\limits_{j \geq 0} \sum\limits_{k=2}^{n-1} \binom{n^{2}-k^{2}-1}j u(k-1) x^{k+j-2}  \notag \\ 
& = \sum\limits_{m \geq 0} \sum\limits_{k=2}^{n-1} \binom{n^{2}-k^{2}-1}{m-k+2} u(k-1) x^m =
\sum\limits_{m = 0}^{n^2-5} \sum\limits_{k=2}^{n-1} \binom{n^{2}-k^{2}-1}{m-k+2} u(k-1) x^m. \notag 
\end{align}
Here, we have set $m=k+j-2$, and we note that, for $2\leq k\leq n-1$, the condition $0\leq m-k+2 \leq n^{2}-k^{2}-1$ amounts to $0 \leq m \leq n^{2}-k(k-1)-3 \leq n^{2}-5$.
\end{proof} 

\begin{theorem}\label{Th2} For $1\leq h\leq 2n+1$ and $n\geq 2$, we have
\begin{align}\label{30}
u(n)= & \binom{n^{2}+h-1}{n-1}+\binom{n^{2}+h-2}{n-1}-\sum\limits_{k=2}^{n-1}
\binom{n^{2}-k^{2}+h-1}{n-k+1}u\left( k-1\right) \notag \\
&-\left( h-1\right) u\left( n-1\right).
\end{align}
\end{theorem}
\begin{proof}
The constant coefficient of $p_{n^{2}+h}(x)=\sum\limits_{k=n+1}^{n^{2}+h+1}v(k,n^{2}+h)x^{k-n-1}$ is 
$$p_{n^{2}+h}\left( 0\right) =v\left( n+1,n^{2}+h\right) =u(n),$$
by \eqref{7}. So $u(n)$ is the coefficient of $x^{n-1}$ in $x^{n-1}p_{n^{2}+h}\left( x\right)$.
Moreover by \eqref{28}, we have 
$$x^{n-1}p_{n^{2}+h}\left( x\right)  =\left( x+1\right) ^{n^{2}+h-1}+\left( x+1\right) ^{n^{2}+h-2}-\left( x+1\right) ^{h}T_{n}\left( x\right) 
-u\left( n-1\right) x^{n-2}\left( x+1\right) ^{h-1};$$  
and, by binomial expansions, we get 
\begin{align}
(x+1)^h T_n(x)& = \sum\limits_{k=2}^{n-1}u\left( k-1\right) x^{k-2}\left( x+1\right)^{n^{2}-k^{2}+h-1} = \notag \\ 
& = \sum\limits_{k=2}^{n-1}u(k-1) \sum\limits_{j \geq 0} \binom {n^2- k^2+h-1} j x^{j+k-2}.  \notag
\end{align} 
Therefore 
\begin{align} 
& x^{n-1}p_{n^{2}+h}\left( x\right)= \sum\limits_{k=0}^{n^{2}+h-1}\binom{^{n^{2}+h-1}}{k}x^{k}+\sum\limits_{k=0}^{n^{2}+h-2}\binom{^{n^{2}+h-2}}{k}x^{k} \notag \\
& - \sum\limits_{j \geq 0} \sum\limits_{k=2}^{n-1} \binom {n^2- k^2+h-1} j u(k-1) x^{j+k-2} -u\left( n-1\right) \sum\limits_{k=0}^{h-1}\binom{^{h-1}}{k}x^{k+n-2}. \notag 
\end{align}
So the coefficient of $x^{n-1}$ in $x^{n-1}p_{n^{2}+h}\left( x\right)$ 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}-\sum\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}+h-1}{n-k+1}u\left( k-1\right) 
-\left( h-1\right) u\left( n-1\right).$$
The result follows by identifying the two expressions for the coefficient of $x^{n-1}$. 
\end{proof}

\begin{corollary}\label{Cor7} For $n\geq 2$, we have
\begin{equation}\label{31}
u(n)=\binom{n^{2}}{n-1}+\binom{n^{2}-1}{n-1}
-\sum\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}}{n-k+1}u\left( k-1\right).
\end{equation}
\end{corollary}
\begin{proof} This is the special case $h=1$ of \eqref{30}. 
\end{proof}

\begin{corollary}\label{Cor8} For $n\geq 2$ and $0\leq h\leq 2n,$ we have
\begin{equation}\label{32}
u(n-1)=\binom{n^{2}+h-1}{n-2}+\binom{n^{2}+h-2}{n-2}
-\sum\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}+h-1}{n-k}u(k-1).
\end{equation}
\end{corollary}
\begin{proof}
Replacing $h$ by $h+1$ in \eqref{30}, we get
\begin{equation}\label{33}
u(n)=\binom{n^{2}+h}{n-1}+\binom{n^{2}+h-1}{n-1}
-\sum\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}+h}{n-k+1}u\left( k-1\right)
-hu\left( n-1\right).
\end{equation}
Then, substracting \eqref{30} from \eqref{33}, and using the fundamental relation for binomial coefficients, 
\begin{equation}\label{34}
\binom{n}{k}-\binom{n-1}{k}=\binom{n-1}{k-1},
\end{equation}
we get the desired result.
\end{proof}

\begin{corollary}\label{Cor9} For $n\geq 3$ and $0\leq h\leq 2n-1$, we have
\begin{equation}\label{35}
\sum\limits_{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}.
\end{equation}
\end{corollary}
\begin{proof}
It follows from \eqref{32} that the expression
$$F(n,h)=\binom{n^{2}+h-1}{n-2}+\binom{n^{2}+h-2}{n-2}-\sum
\limits_{k=2}^{n-1}\binom{n^{2}-k^{2}+h-1}{n-k}u(k-1)$$
is independent of $\ 0\leq h\leq 2n$. Therefore $F(n,h)-F(n,h+1)=0$ for $0\leq h\leq 2n-1$, which, in view of \eqref{34}, 
yields the desired result.
\end{proof}

\begin{corollary}\label{Cor10} For $n\geq 3$ and $2\leq k\leq n-1$, we have the expression in ``closed form''  
\begin{equation}\label{36}
u(k-1)=\dfrac{\Delta _{n}(k)}{\Delta _{n}}, 
\end{equation} 
where $\Delta _{n}$ is the $\left( n-2\right) \times \left( n-2\right)$ determinant
$$\Delta _{n}=\det \left( \left( \binom{n^{2}-k^{2}+h-1}{n-k-1} \right) _{\substack{ 0\leq h\leq n-3 \\ 2\leq k\leq n-1}}\right)$$ 
and $\Delta _{n}(k)$ is the determinant obtained by replacing in $\Delta _{n}$ the $k$-th column by the column 
$$\left( \binom{n^{2}+h-1}{n-3}+\binom{n^{2}+h-2}{n-3}\right) _{0\leq h\leq n-3}.$$
\end{corollary}
\begin{proof} 
The relations \eqref{35}, restricted to $0\leq h\leq n-3$, give a system of $n-2$
linear equations into the $n-2$ unknowns $u(1), u(2),\ldots , u(n-2)$, which can be written
\begin{equation}\label{37}
\sum\limits_{k=2}^{n-1}a_{n}\left( k,h\right) u(k-1)=b_{n}(h), \quad 0\leq h\leq n-3,
\end{equation}
with 
$$a_{n}(k,h)=\binom{n^{2}-k^{2}+h-1}{n-k-1}\quad \text {and} \quad 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)$. 
\end{proof}

\begin{remark}\label{Rem4} Computations of a number of values of $\Delta_n$ suggested that $\Delta_n = \pm 1$. We have since proved that 
$\Delta_n = (-1)^{(n-2)(n-3)/2}$.
\end{remark}

\begin{remark}\label{Rem4'} Computations of $f(n)= \log_2 u(n)$ and of $g(n)= \frac {f(n)}n$ for $1 \leq n \leq 105$ seem to indicate that there exist 
constants $0< c_1 <c_2$ such that $c_1 n \leq g(n) \leq c_2 n$, i.e. $c_1 n^2 \leq f(n) \leq c_2 n^2$, so that $2^{c_1 n^2} \leq u(n) \leq 2^{c_2 n^2}$, for large enough $n$. 

 
\end{remark}

\begin{remark}\label{Rem5} The expression \eqref{37} gives another method for computing the
values of $u(n)$ quite different from the one given in \eqref{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.
\end{remark}


\begin{remark}\label{Rem6} Here are some of the steps that led us to the polynomials $p_t$ and $T_n$. We used \emph{generating functions} and their ability to hold data 
\emph{quite tight}. Set $I= \mathbb N \times \mathbb N$ and introduce the following formal series:
$$U(x,y)= \sum_{(n,t) \in I} u(n,t)x^ny^t, \quad  V(x,y)= \sum_{(n,t) \in I} v(n,t)x^ny^t, \quad G(n,y)= \sum_{t\geq 0} u(n,t)y^t,$$
and 
$$P(x,y)= \sum_{n \geq 1} u(n-1)x^ny^{n^2+1}.$$
Thus 
$$U(x,y)= \sum_{n \geq 0} G(n,y)x^n.$$
Also, by \eqref{3}
$$G(n,y)= \sum_{0\leq t<n^2} u(n,t)y^t +u(n) \frac {y^{n^2}}{1-y}, \quad \text{for}\ n\geq 0.$$
In particular, 
$$G(0,y) = \sum_{t\geq 0} y^t = \frac 1{1-y}.$$ 
Now, using some formulas established in section 2, we obtain relations among these generating functions. Thus, by \eqref{4} and \eqref{9}, we have 
$$V(x,1)= \sum_{n \geq 0, t\geq 0} v(n,t)x^n =  \sum_{t\geq 0} v(0,t) + \sum_{n\geq 1} \sum_{t=0}^{\infty} v(n,t) x^n = \sum_{n\geq 1} u(n)x^n. $$
Similarly using \eqref{12}, we get 
$$(1-y)U(x,y) = V(x,y)+1,$$
and using \eqref{15}, we get 
$$(1-y-xy)V = x- P, \quad (1-y)(1-y-xy)U = 1+x-y-xy -P.$$
Then, introducing $F(x,y)= \sum_{t\geq n-1 \geq 0} \binom t{n-1} x^ny^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 \emph{pascalian} tableau for the $v(n,t)$'s. To extract information from those relations, some heavy analytical machinery is probably needed.

The \emph{truncated pascalian} triangle of the $v(n,t)$'s, given in
Table~\ref{tab0}, starts as follows (where the points represent $0$'s):

\begin{table}
\begin{center}
\begin{tabular}{cccccccc}
$t/n$&$1$ & $2$ & $3$ & $4$ & $5$ &$6$ & $7$
\\
0 & 1 \\
1 & 1 & 1\\
2 & $\cdot$ & 2 & 1\\
3 & $\cdot$ & 2 & 3 & 1\\
4 & $\cdot$ & 2 & 5 & 4 & 1\\
5 & $\cdot$ & $\cdot$ & 7 & 9 & 5 & 1\\
6 & $\cdot$ & $\cdot$ & 7 & 16 & 14 & 6 & 1\\
7 & $\cdot$ & $\cdot$ & 7 & 23 & 30 & 20 & 7\\
8 & $\cdot$ & $\cdot$ & 7 & 30 & 53 & 50& 27\\
9 & $\cdot$ & $\cdot$ & 7 & 37 & 83 & 103& 77\\
10 & $\cdot$ &$\cdot$ &$\cdot$ &44& 120\\
11 & $\cdot$ & $\cdot$ & $\cdot$ &44 & 164\\
12 & $\cdot$ & $\cdot$ & $\cdot$ &44 & 208\\
13 & $\cdot$ & $\cdot$ & $\cdot$ &44 & 252 \\
14 & $\cdot$ & $\cdot$ & $\cdot$&44  & 296 \\
15 & $\cdot$ & $\cdot$ & $\cdot$&44  & 340\\
16 & $\cdot$ & $\cdot$ & $\cdot$ &44 & 384\\
17 & $\cdot$ & $\cdot$ & $\cdot$&$\cdot$ &  428\\
18 & $\cdot$ & $\cdot$ & $\cdot$ &$\cdot$ & 428\\
\end{tabular}  
\end{center}
\caption{Truncated pascalian table}
\label{tab0}
\end{table}

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:
\begin{align}
p_1(x) & = ((1+x)x -0)/x =1+x, \notag \\
p_2(x) & = ((1+x)(1+x) -1)/x = 2+x, \notag \\
p_3(x) & = (2+x)(1+x) = 2+3x+x^2, \notag \\ 
p_4(x) & = (2+x)(1+x)^2= 2+5x+ 4x^2 +x^3, \notag \\
p_5(x) & = ((2+x)(1+x)^3 -2)/x = 7+9x+5x^2 +x^4. \notag 
\end{align}

A look at the list strongly suggested the introduction of the $T_n$'s. That is about everything.

\end{remark}


\section {Acknowledgment}\label{acknowledge}
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. 


\begin{thebibliography}{9}


\bibitem{E-F} P. Erd\H{o}s and W. H. J. Fuchs, On a problem of additive
number theory, {\it J. London Math. Soc.} \textbf{31} (1956), 67--73.

\bibitem{E-T} P. Erd\H{o}s and P. Tur\'an, On a problem of Sidon in
additive number theory, {\it J. London Math. Soc.} \textbf{16} (1941),
212--215.

\bibitem{CET} G. Grekos, L. Haddad, C. Helou, and J. Pihko, The class
of Erd\H{o}s-Tur\'an sets, {\it Acta Arith.} \textbf{117} (2005),
81--105.

\bibitem{GET} G. Grekos, L. Haddad, C. Helou, and J. Pihko, On the
general Erd\H{o}s-Tur\'an conjecture, 
{\it Int. J. Comb.} (2014), Article ID 826141.

\bibitem{H-R} H. Halberstam and K. F. Roth, {\it Sequences}, Oxford
Clarendon Press, 1966.

\bibitem{OEIS} N. J. A. Sloane, {\it The On-line Encyclopedia of Integer Sequences}, \url{http://oeis.org}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 05A15, 05A19, 11B65, 11B75.

\noindent \emph{Keywords:} finite sequence, binomial coefficient,
combinatorics, enumeration.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A242105}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 24 2014;
revised versions received  September 2 2014; January 12 2015.
Published in {\it Journal of Integer Sequences}, January 13 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}