\input amstex
\documentstyle{amsppt}
\magnification=\magstephalf
\pagewidth{6.25truein}
\pageheight{9.25truein}
\parskip=10pt
\voffset=0pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\nologo

\topmatter
\leftheadtext{\hskip 8pt \smalltt INTEGERS: \smallrm Electronic Journal of Combinatorial
Number Theory \smalltt 2 (2002) \#A04\hfill}
\rightheadtext{\hskip 8pt \smalltt INTEGERS: \smallrm Electronic Journal of Combinatorial
Number Theory \smalltt 2 (2002) \#A04\hfill}
\def\N{\Bbb N}
\def\Z{\Bbb Z}
\def\zp{\Z^+}
\def\Q{\Bbb Q}
\def\R{\Bbb R}
\def\C{\Bbb C}
\def\l{\left}
\def\r{\right}
\def\bg{\bigg}
\def\({\bg(}
\def\[{\bg[}
\def\){\bg)}
\def\]{\bg]}
\def\t{\text}
\def\f{\frac}
\def\mo{\roman{mod}}
\def\em{\emptyset}
\def\se {\subseteq}
\def\sp {\supseteq}
\def\sm{\setminus}
\def\Lr{\Leftrightarrow}
\def\ar{\Rightarrow}
\def\Ar{\Longrightarrow}
\def\bi{\binom}
\def\eq{\equiv}
\def\cs{\cdots}
\def\ls{\leqslant}
\def\gs{\geqslant}
\def\al{\alpha}
\def\ve{\varepsilon}
\def\da{\delta}
\def\Da{\Delta}
\def\la{\lambda}
\def\ta{\theta}
\def\mc{m\t{-cover of}\ \Z}
\def\e{2\pi i}
\def\n{\frac1{n_s}}
\def\mn{\f{m_s}{n_s}}
\def\si{\sum_{s\in I}}
\def\ok{\{1,\cdots,k\}}
\def\kt{\ok\sm\{t\}}
\def\nn{n_1,\cdots,n_k}
\def\bi{\binom}
\def\Proof{\noindent{\it Proof}}
\def\M#1#2{\thickfracwithdelims[]\thickness0{#1}{#2}}
\def\MM#1#2#3#4{\l(\matrix #1&#2\\#3&#4\endmatrix\r)}
\def\Proof{\noindent{\it Proof}}
\def\Def{\medskip\noindent{\it Definition}}
\def\Nota{\medskip\noindent{\it Notation}}
\def\Remark{\medskip\noindent{\it  Remark}}
\def\Ack{\medskip\noindent {\bf Acknowledgment}}
\endtopmatter

\document
\centerline{\bf A CURIOUS IDENTITY INVOLVING BINOMIAL COEFFICIENTS}
\vskip 20pt
\centerline{\smallit Zhi-Wei Sun
\footnote{Supported by
the Teaching and Research Award Program for Outstanding Young Teachers
in Higher Education Institutions of MOE, and
the National Natural Science Foundation of P. R. China.
\newline\indent  2000 {\it Mathematics Subject Classification}.
 Primary 05A19; Secondary 05A10, 11B65.}
Department of Mathematics, Nanjing University,
Nanjing 210093, P. R. China}
\centerline{\tt zwsun\@nju.edu.cn}
%\vskip 20pt
%\centerline{\smallit Author Two\footnote{any footnote here}, Two University, Someplace, Country AAAAA }
%\centerline{\tt me\@math.one.edu} (optional)
\vskip 30pt
\centerline{\smallit Received: 11/28/01, Accepted: 2/13/02, Published: 2/13/02}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
 Let $m$ be a nonnegative integer.
For integers $0\ls k\ls m$ and $n\gs0$
we show the following curious identity
$$\align&(n+2(m-k)+1)\sum_{i=k}^m(-1)^i\bi{m+n+i}{m-i}\bi{2i}{k+i}
\\=&(-1)^k\sum_{i=0}^{m-k}\bi{m+n-k+i}{m-k-i}(-4)^i+(-1)^kn\bi{m+n-k}n.
\endalign$$
Equivalently, we have
$$(x+m+1)\sum_{i=0}^m(-1)^i\bi{x+y+i}{m-i}\bi{y+2i}i
-\sum_{i=0}^m\bi{x+i}{m-i}(-4)^i=(x-m)\bi xm.$$

\baselineskip=15pt
\vskip 30pt



\subhead \nofrills{\bf 1. Introduction}\endsubhead


 For integers $m>0$, $n\gs 0$ and $r$,  let
 $$T^n_{r(m)}=\sum\Sb 0\ls k\ls n\\ k\eq r\ (\mo\ m)\endSb\bi nk.$$
 Such sums were investigated and applied by the author and his twin brother
 Zhi-Hong Sun in [SS], [S1], [S2], [Su1] and [Su2].
 In the study of the generating function of
 the sequence $\{T^n_{[n/2](m)}\}_{n=0}^{+\infty}$
 where $[\cdot]$ is the greatest integer function,
 Zhi-Hong Sun posed the following conjecture:

{\it If $m,n\in\N=\{0,1,2,\cs\}$ and $m\ls n$, then
$$\sum_{i=0}^m(-1)^i\bi{n+i}{m-i}\l((m+n+1)\bi{2i}i-4^i\r)
=(n-m)\bi nm.\tag1.1$$
In other words,  for any $m,n\in\N$ we have
$$\sum_{i=0}^m(-1)^i\bi{m+n+i}{m-i}\l((2m+n+1)\bi{2i}i-4^i\r)
=n\bi {m+n}n.\tag1.2$$ }

The above conjecture is far from transparent and seems to be somewhat
sophisticated. In this paper will show an extension of the conjecture
by means of generating functions, Chebyshev polynomials
and double recursions.

For convenience we set
 $$A_k(m,n)=\sum_{i=k}^m(-1)^i\bi{m+n+i}{m-i}\bi{2i}{k+i}
 \ \ \ \t{for}\ k,m,n\in\N\ \t{with}\ k\ls m\tag1.3$$
 and
$$B(m,n)=\sum_{i=0}^m\bi{m+n+i}{m-i}(-4)^i
\ \ \ \ \t{for}\ m,n\in\N.\tag1.4$$

Our main result is as follows:
\proclaim{Theorem 1.1} If $k,m,n\in\N$ and $k\ls m$, then
$$(n+2(m-k)+1)A_k(m,n)-(-1)^kB(m-k,n)=(-1)^kn\bi{m+n-k}{n}.\tag1.5$$
\endproclaim

We will provide recursions for $A_k(m,n)$ and $B(m,n)$ in the next section,
 and prove Theorem 1.1 in Section 3.


Recall that
$$\bi x0=1\ \ \t{and}\ \ \bi xn=\f{x(x-1)\cs(x-n+1)}{n!}\
\ \ \t{for}\ n=1,2,3,\cs.$$

Theorem 1.1 has the following equivalent version.

\proclaim{Theorem 1.2} For each $m=0,1,2,\cs$ we have
$$\aligned&(x+m+1)\sum_{i=0}^m(-1)^i\bi{x+y+i}{m-i}\bi{y+2i}{i}
\\=&\sum_{i=0}^m\bi{x+i}{m-i}(-4)^i+(x-m)\bi xm.
\endaligned\tag1.6$$
\endproclaim

\vskip 30pt

\subhead \nofrills{\bf 2. Double Recursions for $A_k(m,n)$ and $B(m,n)$}\endsubhead

\proclaim{Lemma 2.1} Let $k,m\in\N$ and $k\ls m$. Then
$A_k(m,0)=(-1)^m.$
\endproclaim
\Proof. For $i\in\Z$ with $k\ls i\ls m$, clearly
$$\bi{m+i}{m-i}\bi{2i}{k+i}=\f{(m+i)!}{(m-i)!(2i)!}\times\f{(2i)!}{(k+i)!(i-k)!}
=\bi{m+i}{k+i}\bi{m-k}{m-i}.$$
So
$$\align(-1)^mA_k(m,0)=&\sum_{i=k}^m(-1)^{m-i}\bi{m+i}{m-i}\bi{2i}{k+i}
\\=&\sum_{i=k}^m(-1)^{m-i}\bi{m-k}{m-i}\bi{(m-k)+k+i}{k+i}.
\endalign$$
This is the coefficient of $x^{k+m}$ in the power series of
$$(1-x)^{m-k}\sum_{n=0}^{+\infty}\bi{m-k+n}{n}x^n=(1-x)^{m-k}\cdot\f1{(1-x)^{m-k+1}}
=\f1{1-x}\ \ (|x|<1).$$
So $(-1)^mA_k(m,0)=1$. This ends the proof. \qed

\proclaim{Lemma 2.2} For $m\in\N$ we have
$B(m,0)=(-1)^m(2m+1).$
\endproclaim
\Proof. For $n=0,1,2,\cs$ the $n$th Chebyshev polynomial $U_n(x)$
of the second kind is defined by
$$\sin((n+1)\theta)=\sin\theta\cdot U_n(\cos\theta).$$
It is well-known that
$$U_n(x)=\sum_{j=0}^{[n/2]}(-1)^j\bi{n-j}j(2x)^{n-2j}.$$


In view of the above,
$$\align 2m+1=&\lim_{\theta\to0}\f{\sin((2m+1)\theta)}{\sin\theta}
=\lim_{\theta\to0}U_{2m}(\cos\theta)=U_{2m}(\cos0)=U_{2m}(1)
\\=&\sum_{j=0}^{m}(-1)^j\bi{2m-j}j2^{2m-2j}
\\=&\sum_{i=0}^m(-1)^{m-i}\bi{m+i}{m-i}4^i=(-1)^mB(m,0).
\endalign$$
We are done. \qed

\proclaim{Lemma 2.3} Let $k,m,n\in\N$ and $k\ls m$. Then
$$A_k(m+1,n+1)=A_k(m+1,n)+A_k(m,n+1)$$
and
$$B(m+1,n+1)=B(m+1,n)+B(m,n+1).$$
\endproclaim
\Proof. For any $a_0,a_1,\cs,a_{m+1}\in\Z$ we have
$$\sum_{i=0}^{m+1}\bi{m+1+n+1+i}{m+1-i}a_i
=\sum_{i=0}^{m+1}\bi{m+1+n+i}{m+1-i}a_i
+\sum_{i=0}^m\bi{m+n+1+i}{m-i}a_i.$$
So the desired equalities follow. \qed

\proclaim{Theorem 2.1} Let $k,m,n\in\N$ and $k\ls m$.
Then we have
$$\cases A_k(m,0)=(-1)^m &
\\A_k(k,n)=(-1)^k &
\\ A_k(m+1,n+1)=A_k(m+1,n)+A_k(m,n+1)&\endcases\tag2.1$$
and
$$\cases B(m,0)=(-1)^m(2m+1)&
\\B(0,n)=1\\B(m+1,n+1)=B(m+1,n)+B(m,n+1).&
\endcases \tag2.2$$
\endproclaim
\Proof. In view of Lemmas 2.1|2.3, it suffices to check equalities
$A_k(k,n)=(-1)^k$ and $B(0,n)=1$, which can be easily seen.
This concludes the proof. \qed

\vskip 30pt

\subhead \nofrills{\bf 3. Proofs of Theorems 1.1 and 1.2}\endsubhead

\proclaim{Lemma 3.1} For $k,m,n\in\N$ with $k\ls m$, we have
$$A_k(m,n)+A_k(m+1,n)=(-1)^k\bi{m-k+n}{m-k+1}\tag3.1$$
and
$$(-1)^mA_k(m,n)=\sum_{i=0}^{m-k}(-1)^i\bi{n+i-1}i.\tag3.2$$
\endproclaim
\Proof. i) We fix $k\in\N$ and use induction on $mn$ to show (3.1).

If $n=0$ or $m=k$ then (3.1) holds, for,
$$A_k(m,0)+A_k(m+1,0)=(-1)^m+(-1)^{m+1}=0=(-1)^k\bi{m-k}{m-k+1}$$
and
$$\align A_k(k,n)+A_k(k+1,n)=&
(-1)^k+\sum_{i=k}^{k+1}(-1)^i\bi{k+1+n+i}{k+1-i}\bi{2i}{k+i}
\\=&(-1)^k+(-1)^k(2k+n+1)+(-1)^{k+1}\bi{2k+2}{2k+1}
\\=&(-1)^k(1+2k+n+1-2k-2)=(-1)^k\bi n1.
\endalign$$

Clearly both $m(n+1)$ and $(m+1)n$ are less than $(m+1)(n+1)$.
Assume that $$A_k(m,n+1)+A_k(m+1,n+1)=(-1)^k\bi{m-k+n+1}{m-k+1}$$
and $$A_k(m+1,n)+A_k((m+1)+1,n)=(-1)^k\bi{m+1-k+n}{m+1-k+1}.$$
With the help of Lemma 2.3,
$$\align &A_k(m+1,n+1)+A_k((m+1)+1,n+1)
\\=&A_k(m+1,n)+A_k(m,n+1)+(A_k(m+2,n)+A_k(m+1,n+1)
\\=&(A_k(m+1,n)+A_k(m+2,n))+(A_k(m,n+1)+A_k(m+1,n+1))
\\=&(-1)^k\bi{m-k+n+1}{m-k+2}+(-1)^k\bi{m-k+n+1}{m-k+1}
\\=&(-1)^k\bi{m+1-k+n+1}{m+1-k+1}.
\endalign$$

In view of the above, we have proved (3.1).

ii) Observe that
$$\align(-1)^mA_k(m,n)-(-1)^kA_k(k,n)
=&\sum_{k\ls l<m}\l((-1)^{l+1}A_k(l+1,n)-(-1)^lA_k(l,n)\r)
\\=&\sum_{k\ls l<m}(-1)^{l+1}\l(A_k(l+1,n)+A_k(l,n)\r).
\endalign$$
Applying (2.1) and (3.1) we then obtain that
$$\align(-1)^mA_k(m,n)=&(-1)^k(-1)^k+(-1)^k\sum_{k\ls l<m}
(-1)^{l+1}\bi{l-k+n}{l-k+1}
\\=&\sum_{i=0}^{m-k}(-1)^i\bi{n+i-1}i.
\endalign$$
This ends the proof.  \qed

\Remark\ 3.1. Let $n\in\N$. It is well-known that
$$\f1{(1-x)^n}=\sum_{i=0}^{+\infty}\bi{n-1+i}{i}x^i\ \ \t{for}\
x\in(-1,1).$$
An identity of Shi-Jie Zhu (cf. (4.3.8) of [B]) asserts that
$$\sum_{i=0}^l\bi{n-1+i}i=\bi{l+n}l\ \ \t{for}\ l=0,1,2,\cs.$$
Thus, $A_k(m,n)$ (with $k,m\in\N$ and $k\ls m$)
is interesting in view of (3.2).

\medskip
\noindent{\it Proof of Theorem 1.1}.
Fix $k\in\N$. Below we use induction on $mn$ to show that (1.5)
holds for $m\gs k$ and $n\gs0$.

If $m\gs k$ and $n=0$, then (1.5) is valid, for
$$\align&(2(m-k)+1)A_k(m,0)-(-1)^kB_k(m-k,0)
\\=&(2(m-k)+1)(-1)^m-(-1)^k(-1)^{m-k}(2(m-k)+1)=0.
\endalign$$
In the case $m=k$ and $n\in\N$, (1.5) also holds because
$$(n+1)A_k(k,n)-(-1)^kB(0,n)=(n+1)(-1)^k-(-1)^k\times1=(-1)^kn.$$

Now let $m,n\in\N$ and $m\gs k$. Put $m'=m+1$ and $n'=n+1$.
Assume that
$$(n'+2(m-k)+1)A_k(m,n')-(-1)^kB(m-k,n')=(-1)^kn'\bi{m-k+n'}{n'}$$
and
$$(n+2(m'-k)+1)A_k(m',n)-(-1)^kB(m'-k,n)=(-1)^kn\bi{m'-k+n}{n}.$$
Then
$$\align &(n'+2(m'-k)+1)A_k(m',n')-(-1)^kB(m'-k,n')
\\=&A_k(m',n')+(n+2(m-k)+3)(A_k(m,n')+A_k(m',n))
\\&-(-1)^k(B(m-k,n')+B(m'-k,n))
\\=&A_k(m',n')+A_k(m,n')+(n'+2(m-k)+1)A_k(m,n')-(-1)^kB(m-k,n')
\\&+(n+2(m'-k)+1)A_k(m',n)-(-1)^kB(m'-k,n)
\\=&(-1)^k\bi{m-k+n'}{m-k+1}+(-1)^kn\bi{m'-k+n}{n}+(-1)^kn'\bi{m-k+n'}{n'}
\\=&(-1)^kn'\(\bi{m-k+n'}{n}+\bi{m-k+n'}{n'}\)
=(-1)^kn'\bi{m'-k+n'}{n'}.
\endalign$$

By the above, we have proved Theorem 1.1. \qed

\medskip
\noindent{\it Proof of Theorem 1.2}.
By Theorem 1.1, for any $k,n=0,1,2,\cs$,
we have
$$\align&(n+2m+1)\sum_{i=k}^{k+m}(-1)^i\bi{k+m+n+i}{k+m-i}\bi{2i}{k+i}
\\=&(-1)^{k}\sum_{i=0}^m\bi{m+n+i}{m-i}(-4)^i+(-1)^{k}n\bi {m+n}n,
\endalign$$
i.e.,
$$\align&(n+2m+1)\sum_{j=0}^m(-1)^j\bi{2k+m+n+j}{m-j}\bi{2k+2j}{2k+j}
\\=&\sum_{i=0}^m\bi{m+n+i}{m-i}(-4)^i+n\bi {m+n}m.
\endalign$$
Write   $$P(x,y)=\sum_{i=0}^m(-1)^i\bi{x+y+i}{m-i}\bi{y+2i}i
=\sum_{i=0}^mP_i(x)y^i$$
and $$Q(x)=\sum_{i=0}^m\bi{x+i}{m-i}(-4)^i+(x-m)\bi xm.$$
Then, for any given integer
$t\gs m$, the polynomial equation
$$\sum_{i=0}^m(t+m+1)P_i(t)y^i=P(t,y)=Q(t)$$
has solutions $y=0,2,4,\cs$, hence
$0=(t+m+1)P_0(t)-Q(t)=P_1(t)=\cs=P_m(t)$.
Therefore
$$(x+m+1)P_0(x)=Q(x)\ \ \t{and}\ P_i(x)=0\ \t{for}\ 1\ls i\ls m.$$
It follows that $(x+m+1)P(x,y)=Q(x).$
We are done. \qed



\subhead \nofrills{\bf References}\endsubhead

\widestnumber\key{SSSS}



\ref\key B\by R. A. Brualdi\book Introductory Combinatorics\publ
Elsevier North-Holland, Amsterdam\yr 1977\endref
\ref\key S1\by Z.-H. Sun\paper Combinatorial sum $\sum_{k\eq r\ (\mo\ m)}\bi nk$ and its
applications in number theory.I\jour Nanjing Univ. J. Math. Biquarterly\vol9\yr1992\issue2
\pages227--240\endref
\ref\key S2\by Z.-H. Sun\paper Combinatorial sum $\sum_{k\eq r\ (\mo\ m)}\bi nk$ and its
applications in number theory.II\jour Nanjing Univ. J. Math. Biquarterly\vol10\yr1993
\issue1\pages105--118\endref
\ref\key SS\by Z.-H. Sun and Z.-W. Sun\paper Fibonacci numbers and
Fermat's last theorem \jour Acta Arith.\vol60\yr1992\pages
371--388\endref
\ref\key Su1\by Z.-W. Sun\paper A congruence for primes
\jour Proc. Amer. Math. Soc.\vol123\yr1995
\pages1341--1346\endref
\ref\key Su2\by Z.-W. Sun\paper On the sum $\sum_{k\eq r\ (\mo\ m)}\bi nk$
and related congruences\jour Israel J. Math.\vol 121\yr 2001\finalinfo in press\endref



\enddocument


.