\begin{document}
 \baselineskip=17pt
\hbox{Preprint}
\medskip

\title
[Some super congruences involving binomial coefficients] {Some Super
congruences involving binomial coefficients}

\author
[Hui-Qin Cao and Zhi-Wei Sun] {Hui-Qin Cao and Zhi-Wei Sun*}

\thanks{*Corresponding author. Supported by the National Natural Science Foundation (grant 10871087) of China}

\address{(Hui-Qin Cao) Department of Applied Mathematics, Nanjing Audit University,
Nanjing 211815, People's Republic of China} \email{caohq@nau.edu.cn}
\address {(Zhi-Wei Sun) Department of Mathematics, Nanjing
University, Nanjing 210093, People's Republic of China}
\email{zwsun@nju.edu.cn}

\keywords{Congruences, binomial coefficients, Lucas sequences,
central trinomial coefficients
\newline \indent 2010 {\it Mathematics Subject Classification}. Primary 11B65; Secondary 05A10, 11A07, 11B39, 11S99.}

 \begin{abstract} Let $p>3$ be a prime. We show that
 $$T_{p-1}\eq\l(\f p3\r)3^{p-1}\pmod{p^2},$$
 where the central trinomial coefficient $T_n$ is the constant term in the expansion of $(1+x+x^{-1})^n$.
 We also prove three congruences conjectured by Sun one of which is as follows:
$$\sum_{k=0}^{p-1}\bi{p-1}k\bi{2k}k((-1)^k-(-3)^{-k})\eq
\l(\f p3\r)(3^{p-1}-1)\ (\mo\ p^3).$$
\end{abstract}

\maketitle

\section{Introduction}

As usual we set $\N=\{0,1,2,\ldots\}$ and $\Z^+=\{1,2,3,\ldots\}$.

Let $A,B\in\Z$. The Lucas sequences $u_n=u_n(A,B)\ (n\in\N)$ and
$v_n=v_n(A,B)\ (n\in\N)$ are defined by
$$
u_0=0, u_1=1, \text{and } u_{n+1}=Au_n-Bu_{n-1}\ (n=1,2,\ldots)
$$
and
$$
v_0=2, v_1=A, \text{and } v_{n+1}=Av_n-Bv_{n-1}\ (n=1,2,\ldots).
$$
The characteristic equation $x^2-Ax+B=0$ has two roots
$$
\alpha=\frac{A+\sqrt{\Delta}}{2}\quad\text{and}\quad\beta=\frac{A-\sqrt{\Delta}}{2},
$$
where $\Delta=A^2-4B$. By induction, one can easily get the
following formulas:
$$(\alpha-\beta)u_n=\alpha^n-\beta^n\quad\text{and}\quad
v_n=\alpha^n+\beta^n.$$ It is well-known that
$$u_p\eq\jacob{\Da}{p}\pmod{p}\quad\text{and}\quad u_{p-\jacob{\Da}{p}}\eq0\pmod{p}$$
for any odd prime $p$ not dividing $B$ (see, e.g., Sun \cite{S09b}),
where $(-)$ denotes the Legendre symbol.

Let $p>3$ be a prime and $m$ be an integer not divisible by $p$. In
a series of papers Z. W. Sun \cite{S09b} \cite{S09d} \cite{S09e}
obtained the following congruences involving binomial coefficients
and Lucas sequences:
\begin{equation}\label{bm}
\sum_{k=0}^{p-1}\frac{\bi{2k}{k}}{m^k}\eq\jacob{\Da}{p}+u_{p-\jacob{\Da}{p}}(m-2,1)\pmod{p^2},
\end{equation}
\begin{equation}\label{pbm}
\sum_{k=0}^{p-1}\bi{p-1}{k}\frac{\bi{2k}{k}}{(-m)^k}\eq\jacob{\Da}{p}(m-4)^{p-1}+\l(1-\frac
m2\r)u_{p-\jacob{\Da}{p}}(m-2,1)\pmod{p^2},
\end{equation}
and
\begin{equation}\label{bbm}
\sum_{k=0}^{(p-1)/2}\frac{\bi{2k}{k}}{m^k}\eq\jacob{\Da}{p}+\jacob{-m}{p}\ov{m}u_{p-\jacob{4-m}{p}}(4,m)\pmod{p^2},
\end{equation}
where $\Delta=m^2-4m$ and $$\ov{m}=\begin{cases}1\quad&\text{if } m\eq4\pmod{p},\\
2\quad&\text{if } \jacob{4-m}{p}=1,\\
2/m\quad&\text{if }  \jacob{4-m}{p}=-1.\end{cases}$$

In \cite{S09d} Sun made a conjecture of three congruences.

In this paper we will confirm Sun's conjectured congruences
involving binomial coefficients and Lucas sequences and prove some
identities. Now we state our main results.

\begin{theorem}
Let $p>3$ be a prime. Then
\begin{equation}\label{tt}
T_{p-1}\eq\l(\f p3\r)3^{p-1}\pmod{p^2}
\end{equation}
and
$$
\sum_{k=0}^{p-1}\bi{p-1}{k}\bi{2k}{k}((-1)^k-(-3)^{-k})\eq\jacob{p}{3}(3^{p-1}-1)\pmod{p^3},
$$
where $T_n(n\in\N)$ are the central trinomial coefficients.
\end{theorem}

\begin{theorem}
Let $p$ be a prime with $p\eq\pm 1\pmod{12}$. Then
$$
\sum_{k=0}^{p-1}\bi{p-1}{k}\bi{2k}{k}(-1)^ku_k(4,1)\eq(-1)^{(p-1)/2}u_{p-1}(4,1)\pmod{p^3}.
$$
\end{theorem}

\begin{theorem}
Let $p$ be a prime with $p\eq\pm 1\pmod{8}$. Then
$$
\sum_{k=0}^{p-1}\bi{p-1}{k}\bi{2k}{k}\frac{u_k(4,2)}{(-2)^k}\eq(-1)^{(p-1)/2}u_{p-1}(4,2)\pmod{p^3}.
$$
\end{theorem}

\begin{theorem}
(a) If $6\ |\ n$, then
\begin{equation}\label{1u}
\sum_{k=0}^n\binom nk\binom{2k}{k}\frac{\jacob k3}{4^k}=0.
\end{equation}

(b) If $n\equiv 3\pmod{6}$, then
\begin{equation}\label{1v}
\sum_{k=0}^n\binom nk\binom{2k}{k}\frac{3[3|k]-1}{4^k}=0.
\end{equation}
\end{theorem}

\begin{theorem}
(a) If $4\ |\ n$, then
\begin{equation}\label{2u}
\sum_{k=0}^n\binom nk\binom{2k}{k}\frac{u_k(2,2)}{(-4)^k}=0.
\end{equation}


(b) If $n\equiv 2\pmod{4}$, then
\begin{equation}\label{2v}
\sum_{k=0}^n\binom nk\binom{2k}{k}\frac{v_k(2,2)}{(-4)^k}=0.
\end{equation}
\end{theorem}

\begin{theorem}
If $3\ |\ n$, then
\begin{equation}\label{3u}
\sum_{k=0}^n\binom nk\binom{2k}{k}\frac{u_k(3,3)}{(-4)^k}=0.
\end{equation}
\end{theorem}

\section{Two important Lemmas}\setcounter{equation}{0}

\begin{lemma}\label{luv}
Let $m\in\Z\setminus\{0\}$. Suppose that $A>0$, $A^2-4B\not=0$ and
$mA+4B=0$. For every $n\in\N$ we have
\begin{equation}\label{uab}
\sum_{k=0}^n\binom
nk\binom{2k}{k}\frac{u_k(A,B)}{m^k}=\frac{d^{n/2}(\alpha^n-(-\beta)^n)}{m^n(\alpha-\beta)}\sum_{k=0}^{\lfloor
n/2\rfloor}\binom{n}{k}\bi{n-k}{k}d^{-k}
\end{equation}
and
\begin{equation}\label{vab}
\sum_{k=0}^n\binom
nk\binom{2k}{k}\frac{v_k(A,B)}{m^k}=\frac{d^{n/2}(\alpha^n+(-\beta)^n)}{m^n}\sum_{k=0}^{\lfloor
n/2\rfloor}\binom{n}{k}\bi{n-k}{k}d^{-k},
\end{equation}
where $d=4+4m/A$.
\end{lemma}

\Proof. For a polynomial $P(x)$, we use $[x^n]P(x)$ to denote the
coefficient of $x^n$ in $P(x)$. It's easy to see that
\begin{align*}
[x^n]((1+\alpha x)^2+mx)^n&=[x^n]\sum_{k=0}^n\binom nk(1+\alpha
x)^{2k}(mx)^{n-k}\\
&=m^n\sum_{k=0}^n\binom nk\binom{2k}{k}\frac{\alpha^k}{m^k}.
\end{align*}
Clearly,
\begin{align*}
[x^n]((1+\alpha x)^2+mx)^n&=[x^n](\alpha^2x^2+(2\alpha+m)x+1)^n\\
&=[x^n]\sum_{\substack{a,b,c\geq0\\a+b+c=n}}\binom{n}{a,b,c}\alpha^{2a}(2\alpha+m)^bx^{2a+b}\\
&=\alpha^{n}\sum_{\substack{a,b\geq0\\2a+b=n}}\binom{n}{a,b,a}\(2+\frac{m}{\alpha}\)^b\\
&=\alpha^{n}\sum_{k=0}^{\lfloor
n/2\rfloor}\bi{n}{k}\bi{n-k}{k}\(2+\frac{m}{\alpha}\)^{n-2k}.
\end{align*}
So we obtain that
\begin{equation}\label{alpha}
m^n\sum_{k=0}^n\binom
nk\binom{2k}{k}\frac{\alpha^k}{m^k}=\alpha^{n}\sum_{k=0}^{\lfloor
n/2\rfloor}\bi{n}{k}\bi{n-k}{k}\(2+\frac{m}{\alpha}\)^{n-2k}.
\end{equation}
Similarly,
\begin{equation}\label{beta}
m^n\sum_{k=0}^n\binom
nk\binom{2k}{k}\frac{\beta^k}{m^k}=\beta^{n}\sum_{k=0}^{\lfloor
n/2\rfloor}\bi{n}{k}\bi{n-k}{k}\(2+\frac{m}{\beta}\)^{n-2k}.
\end{equation}
Since $mA+4B=m(\alpha+\beta)+4\alpha\beta=0$, we have
$4+\frac{m}{\alpha}+\frac{m}{\beta}=0$ and
\begin{align*}
2+\frac{m}{\alpha}=&2+\frac{2m}{A+\sqrt{A^2-4B}}\\
=&2+\frac{2m(\sqrt{A^2+mA}-A)}{mA}\\
=&\frac{2\sqrt{A^2+mA}}{A}=\sqrt{d}.
\end{align*}
Note that $(\alpha-\beta)u_k=\alpha^k-\beta^k$ and
$v_k=\alpha^k+\beta^k$. Combining (\ref{alpha}) and (\ref{beta}) we
get (\ref{uab}) and (\ref{vab}) immediately. \qed

For $n\in\N$ we set $H_n=\sum_{k=1}^n1/k$.

\begin{lemma}
Let $p>3$ be a prime and $d\in\Z$ with $p\nmid d$. Then
\begin{align*}
&\sum_{k=0}^{(p-1)/2}\bi{p-1}{k}\bi{p-1-k}{k}d^{-k}\\
\eq&\jacob{\Da}{p}\(\frac{1-d^{p-1}}{2}+(d-4)^{p-1}\)-\frac{d}{4}u_{p-\jacob{\Da}{p}}(d-2,1)\pmod{p^2},
\end{align*}
where $\Da=d(d-4)$.
\end{lemma}
\Proof. Since $\binom{p-1}{k}\equiv (-1)^k(1-pH_k)\pmod{p^2}$ and
$\binom{p-1-k}{k}\equiv (-1)^k\binom{2k}{k}\pmod{p}$, we have
\begin{align*}
&\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1}{k}\binom{p-1-k}{k}d^{-k}\\
\equiv&\sum_{k=0}^{\frac{p-1}{2}}(-1)^k(1-pH_k)\binom{p-1-k}{k}d^{-k}\\
=&\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1-k}{k}(-d)^{-k}-p\sum_{k=0}^{\frac{p-1}{2}}H_k\binom{p-1-k}{k}(-d)^{-k}\\
\equiv&\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1-k}{k}(-d)^{-k}-p\sum_{k=0}^{\frac{p-1}{2}}H_k\binom{2k}{k}d^{-k}\pmod{p^2}.
\end{align*}

It is well known that
$$u_{n+1}(A,
B)=\sum_{k=0}^{n/2}\bi{n-k}{k}A^{n-2k}(-B)^k\quad\t{for}\quad
n\in\N.$$ So we have
\begin{align*}
\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1-k}{k}(-d)^{-k}=(-d)^{1-p}u_p(-d,d)=d^{1-p}u_p(d,d).
\end{align*}
By [S09a, Lemma 2.4] we have
\begin{equation}
2u_p(d,d)-\jacob{\Da}{p}d^{p-1}\eq
u_p(d-2,1)+u_{p-\jacob{\Da}{p}}(d-2,1)\pmod{p^2}.
\end{equation}
On the other hand, in view of [S09d, (2.6)] we have
\begin{equation}
u_p(d-2,1)-\jacob{\Da}{p}\eq\(\frac
d2-1\)u_{p-\jacob{\Da}{p}}(d-2,1)\pmod{p^2}.
\end{equation}
Combining the above two congruences we immediately get
$$u_p(d,d)\eq\jacob{\Da}{p}\frac{(d^{p-1}+1)}{2}
+\frac{d}{4}u_{p-\jacob{\Da}{p}}(d-2,1)\pmod{p^2}.$$ Thus
\begin{align*}
\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1-k}{k}(-d)^{-k}\eq&\jacob{\Da}{p}\frac{d^{p-1}+1}{2d^{p-1}}+\frac{d}{4d^{p-1}}u_{p-\jacob{\Da}{p}}(d-2,1)\\
\eq&\jacob{\Da}{p}\frac{d^{p-1}+1}{2d^{p-1}}+\frac{d}{4}u_{p-\jacob{\Da}{p}}(d-2,1)\pmod{p^2}.
\end{align*}

Clearly
\begin{align*}
&p\sum_{k=0}^{(p-1)/2}H_k\binom{2k}{k}d^{-k}\\
\equiv&\sum_{k=0}^{(p-1)/2}\left(1-(-1)^k\binom{p-1}{k}\right)\binom{2k}{k}d^{-k}\\
=&\sum_{k=0}^{(p-1)/2}\frac{\binom{2k}{k}}{d^k}-\sum_{k=0}^{(p-1)/2}\binom{p-1}{k}\frac{\binom{2k}{k}}{(-d)^k}\\
=&\sum_{k=0}^{(p-1)/2}\frac{\binom{2k}{k}}{d^k}-\sum_{k=0}^{p-1}\binom{p-1}{k}\frac{\binom{2k}{k}}{(-d)^k}+\sum_{k=\frac{p+1}{2}}^{p-1}\binom{p-1}{k}\frac{\binom{2k}{k}}{(-d)^k}\\
\equiv&\sum_{k=0}^{p-1}\frac{\binom{2k}{k}}{d^k}-\sum_{k=0}^{p-1}\binom{p-1}{k}\frac{\binom{2k}{k}}{(-d)^k}\pmod{p^2}.
\end{align*}
Applying (\ref{bm}) and (\ref{pbm}) we obtain that
\begin{align*}
&p\sum_{k=0}^{(p-1)/2}H_k\binom{2k}{k}d^{-k}\\
\eq&\jacob{\Da}{p}+u_{p-\jacob{\Da}{p}}(d-2,1)-\(1-\frac{d}{2}\)u_{p-\jacob{\Da}{p}}(d-2,1)-\jacob{\Da}{p}(d-4)^{p-1}\\
=&\jacob{\Da}{p}(1-(d-4)^{p-1})+\frac{d}{2}u_{p-\jacob{\Da}{p}}(d-2,1).
\end{align*}

Hence
\begin{align*}
&\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1}{k}\binom{p-1-k}{k}d^{-k}\\
\eq&\jacob{\Da}{p}\(\frac{1-d^{p-1}}{2d^{p-1}}+(d-4)^{p-1}\)-\frac{d}{4}u_{p-\jacob{\Da}{p}}(d-2,1)\\
\eq&\jacob{\Da}{p}\(\frac{1-d^{p-1}}{2}+(d-4)^{p-1}\)-\frac{d}{4}u_{p-\jacob{\Da}{p}}(d-2,1)\pmod{p^2}.
\end{align*}

The proof is now complete. \qed


Note that $\jacob{-3}{p}=\jacob{p}{3}$, $u_{p-\jacob{-1}{p}}(0,1)=0$
and
$$u_{p-\jacob{-3}{p}}(-1,1)=u_{p-\jacob{p}{3}}(-1,1)=(-1)^{p-\jacob{p}{3}-1}u_{p-\jacob{p}{3}}(1,1)=\jacob{p-\jacob{p}{3}}{3}=0.$$
Applying Lemma 2.2 with $d=1, 2, 3$, we get corollary as follows:

\begin{corollary}
Let $p>3$ be a prime. Then
\begin{equation}\label{dd3}
\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1}{k}\binom{p-1-k}{k}3^{-k}\eq\jacob{p}{3}\frac{3-3^{p-1}}{2}\pmod{p^2}.
\end{equation}
\begin{equation}\label{dd2}
\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1}{k}\binom{p-1-k}{k}2^{-k}\eq\jacob{-1}{p}\frac{2^{p-1}+1}{2}\pmod{p^2}.
\end{equation}
\begin{equation}\label{dd1}
\sum_{k=0}^{\frac{p-1}{2}}\binom{p-1}{k}\binom{p-1-k}{k}\eq\jacob{p}{3}3^{p-1}\pmod{p^2}.
\end{equation}
\end{corollary}


\section{Proofs of Theorems 1.1-1.6}\setcounter{equation}{0}

\noindent{\it Proof of Theorem 1.1}. The central trinomial
coefficients $$T_k=\sum_{j=0}^{k}\bi{k}{j}\bi{k-j}{j}\qquad
k=0,1,2,\ldots.$$ In view of (\ref{dd1}) we immediately get
(\ref{tt}).

Clearly $u_{p-1}(4,3)\eq0\pmod{p}$. Apply (\ref{uab}) with $n=p-1,
A=4, B=3, m=-3$ and $d=4+4m/A=1$. By (\ref{dd1}), we obtain that
\begin{align*}
&\sum_{k=0}^{p-1}\binom
{p-1}{k}\binom{2k}{k}(-1)^ku_k(4,3)\\
\eq&\frac{u_{p-1}(4,3)}{(-3)^{p-1}}\sum_{k=0}^{(p-1)/2}\bi{p-1}{k}\bi{p-1-k}{k}\\
\eq&\frac1{3^{p-1}}\jacob{p}{3}3^{p-1}u_{p-1}(4,3)\\
=&\jacob{p}{3}u_{p-1}(4,3)\pmod{p^3}.
\end{align*}
Note that $u_k(4,3)=3^k-1$ for $k\in\N$. We conclude the proof now.
\qed

\noindent{\it Proof of Theorem 1.2}. If $p\eq\pm 1\pmod{12}$ then
$$3^{(p-1)/2}\eq\jacob{3}{p}=(-1)^{(p-1)/2}\jacob{p}{3}=1\pmod{p}.$$
Therefore $u_{p-1}(4,1)\eq0\pmod{p}$ and $3^{p-1}\eq
2\cdot3^{(p-1)/2}-1\pmod{p^2}$. Apply (\ref{uab}) with $n=p-1, A=4,
B=1, m=-1, d=4+4m/A=3$. With the help of (\ref{dd3}), we obtain that
\begin{align*}
&\sum_{k=0}^{p-1}\binom
{p-1}{k}\binom{2k}{k}(-1)^ku_k(4,1)\\
\eq&3^{(p-1)/2}u_{p-1}(4,1)\sum_{k=0}^{(p-1)/2}\bi{p-1}{k}\bi{p-1-k}{k}3^{-k}\\
\eq&3^{(p-1)/2}\jacob{p}{3}\frac{3-3^{p-1}}{2}u_{p-1}(4,1)\\
\eq&(-1)^{(p-1)/2}3^{(p-1)/2}(2-3^{(p-1)/2})u_{p-1}(4,1)\\
\eq&(-1)^{(p-1)/2}u_{p-1}(4,1)\pmod{p^3}.
\end{align*}
\qed

\noindent{\it Proof of Theorem 1.3}. If $p\eq\pm 1\pmod{8}$ then
$$2^{(p-1)/2}\eq\jacob{2}{p}=1\pmod{p}.$$
Therefore $u_{p-1}(4,2)\eq0\pmod{p}$ and $2^{p-1}+1\eq
2\cdot2^{(p-1)/2}\pmod{p^2}$. Put $n=p-1, A=4, B=2, m=-2,
d=4+4m/A=2$ in (\ref{uab}). Applying (\ref{dd2}), we obtain that
\begin{align*}
&\sum_{k=0}^{p-1}\binom
{p-1}{k}\binom{2k}{k}(-1)^ku_k(4,2)\\
\eq&\frac{2^{(p-1)/2}u_{p-1}(4,2)}{(-2)^{p-1}}\sum_{k=0}^{(p-1)/2}\bi{p-1}{k}\bi{p-1-k}{k}2^{-k}\\
\eq&\frac1{2^{(p-1)/2}}\jacob{-1}{p}\frac{1+2^{p-1}}{2}u_{p-1}(4,2)\\
\eq&(-1)^{(p-1)/2}u_{p-1}(4,2)\pmod{p^3}.
\end{align*}
\qed

\noindent{\it Proof of Theorem 1.4}. Put $A=B=1, m=-4$. Then
$mA+4B=0$ and
$$\alpha^2+\alpha\beta+\beta^2=(\alpha+\beta)^2-\alpha\beta=0.$$
Thus $\alpha^3=\beta^3$. Consequently $\alpha^n-(-\beta)^n=0$
provided that $6\ |\ n$ and $\alpha^n+(-\beta)^n=0$ if $n\equiv
3\pmod{6}$. Notice that $u_k(1,1)=(-1)^{k-1}\jacob{k}{3}$ and
$v_k(1,1)=(-1)^k(3[3|k]-1)$. With the help of Lemma \ref{luv} we get
the equations (\ref{1u}) and (\ref{1v}) promptly. \qed

\noindent{\it Proof of Theorem 1.5}. Set $A=B=2, m=-4$. It is easy
to see that $mA+4B=0$ and
$$\alpha^2+\beta^2=(\alpha+\beta)^2-2\alpha\beta=0,$$ that is
$\alpha^2=-\beta^2$. So we have $\alpha^n-(-\beta)^n=0$ provided
that $4\ |\ n$ and $\alpha^n+(-\beta)^n=0$ if $n\equiv 2\pmod{4}$.
By Lemma \ref{luv} we get the equations (\ref{2u}) and (\ref{2v})
promptly.\qed


\noindent{\it Proof of Theorem 1.6}. Let $A=B=3, m=-4$. Clearly
$mA+4B=0$ and
$$\alpha^2-\alpha\beta+\beta^2=(\alpha+\beta)^2-3\alpha\beta=0.$$
Therefore $\alpha^3=-\beta^3$. Hence $\alpha^n-(-\beta)^n=0$
provided that $3\ |\ n$. Applying (\ref{uab}) we obtain the equation
(\ref{3u})  immediately.\qed
{"config": "arxiv", "file": "1006.3069.tex"}