\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}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf On the Divisibility of Generalized \\ \vskip .1in Central Trinomial Coefficients} \vskip 1cm \large Tony~D.~Noe\\ 14025~NW~Harvest~Lane\\ Portland,~OR~~97229\\ USA\\ \href {mailto:noe@sspectra.com} {\tt noe@sspectra.com} \end{center} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \hyphenation {combinatorial} \vskip .2in \begin {abstract} We present several methods of computing sequences of generalized central trinomial coefficients. We generalize the Schur and Holt congruences for Legendre polynomials in order to prove divisibility properties of these sequences and a conjecture of Deutsch and Sagan. % \cite {DS} \end {abstract} %\newtheorem {theorem} {Theorem} %\newtheorem {lemma} {Lemma} \section {Introduction} For integers $a, b,c$, we call the coefficient of $x^n$ in the expression \begin {equation} (a+b x+c x^2)^n \label {Eq.Main} \end {equation} the generalized central trinomial coefficient, $T_n$. The sequences $\{ T_n \}_{n \ge 0}$ have combinatorial interpretations and, as shown in Table 1 at the end of this paper, appear frequently in Sloane's On-Line Encyclopedia of Integer Sequences \cite {Sloane}. By using the binomial theorem twice and the identity $\binom {n} {k} \binom {n-k} {n-2k} = \binom {2k} {k} \binom {n} {2k}$, we obtain \begin {equation} T_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom {2k} {k} \binom {n} {2k} b^{n-2k} (ac)^k. \label {Eq.Basic} \end {equation} Assuming $b$ is fixed, note that for any $a$ and $c$ having a fixed nonzero product, the sequences will be the same. Hence, we assume $a=1$. Because $b=0$ is a degenerate case and the absolute value of $T_n$ is the same for $b$ and $-b$, we can assume $b>0$ for divisibility purposes. As we will see below, an important quantity that determines many properties of the sequence is the the discriminant $d=b^2-4 a c$. There are an infinite number of pairs $(b,c)$ that yield the same discriminant. Also, the discriminant is always of the form $4k$ or $4k+1$ for some integer $k$. We begin by considering several ways of evaluating these sequences. We will see that the representation as values of Legendre polynomials is crucial in studying the divisibility of the sequences by primes. \section {Ordinary Generating Function} Using the solution to an exercise in \cite [page 575] {GKP}, we compute the sequence from the ordinary generating function \begin {equation} \frac {1}{\sqrt {1-2bx+dx^2}} = \sum_{k=0}^{\infty} T_k x^k. \label {Eq.GenFunc} \end {equation} Euler \cite {Euler} found this generating function for the case $a=b=c=1$. Observe that when c is a perfect square, the quadratic in the radical factors into the product of two linear terms $1-(b+2 \sqrt {c})x$ and $1-(b-2 \sqrt {c})x$ having integer coefficients. This factorization allows us to represent equation~\eqref {Eq.GenFunc} as the convolution of two sequences of the form \begin {equation*} \frac {1}{\sqrt {1-f x}} = \sum_{k=0}^{\infty} \frac {1}{4^k} \binom {2k} {k} f^k \end {equation*} for constant $f$. For $f=1$, see sequence \seqnum {A001790}. Forming the convolution, we obtain the interesting \begin {equation*} T_n = \frac {1}{4^n} \sum_{k=0}^{n} \binom {2n-2k} {n-k}\binom {2k} {k} f^k g^{n-k}, \end {equation*} where $f=b+2 \sqrt {c}$ and $g=b-2 \sqrt {c}$ are not required to be integers. \section {Recursion Equation} The exercise in \cite {GKP} states that the recurrence equation for the sequence is \begin {equation} T_0=1, \quad T_1=b, \quad T_n = \frac {(2n-1) b T_{n-1} - (n-1) d T_{n-2}}{n}, \label {Eq.Recur} \end {equation} which provides an efficient formula for computing $T_n$. Euler \cite {Euler} found this recursion equation for the case $a=b=c=1$. Observe that the recursion actually needs only $T_0$ to start; $T_1$ can be computed. The recursion also allows us to show that \begin {equation*} T_{n+1} \equiv b T_n \pmod {n}. \end {equation*} \section {Exponential Generating Function} Using the infinite series expansion of the modified Bessel function of the first kind, \begin {equation*} I_0(x) = \sum_{k=0}^{\infty} \frac {(\frac {1} {4} x^2)^k} {(k!)^2} \end {equation*} and the infinite series expansion of the exponential function, it is not hard to show that the sequence can be computed from the exponential generating function \begin {equation*} e^{b x} I_0(2x \sqrt {c}) = \sum_{k=0}^{\infty} \frac {T_k x^k} {k!}. \end {equation*} \section {Legendre Polynomials} When the discriminant $d$ is nonzero, the sequence can be defined in terms of the Legendre polynomials \begin {equation} T_n = d^{n/2} \; P_n \bigg ( \frac {b} {\sqrt {d}} \bigg ), \label {Eq.Legendre} \end {equation} which is easy to derive from the generating function for Legendre polynomials \begin {equation*} \frac {1}{\sqrt {1-2t x+t^2}} = \sum_{n=0}^{\infty} P_n(x) t^n. \end {equation*} Note that in equation~\eqref {Eq.Legendre}, after multiplying each term of the polynomial $P_n(b / \sqrt {d} )$ by $d^{n/2}$, there will be no occurrences of $\sqrt {d}$ because the degree of the polynomial is $n$ and its terms have either all even or all odd exponents if $n$ is even or odd, respectively. The cases of $d=1$ and $d=0$ have particularly simple forms. When $d=1$, which occurs when $b=2k+1$ and $c=k(k+1)$ for integer $k \ge 0$, we obtain $T_n = P_n(b)$. When $d=0$, equation~\eqref {Eq.Main} can be written as $(1+b x/2)^{2n}$ and the sequence is \begin {equation} T_n = \bigg (\frac {b} {2} \bigg )^n \binom {2n} {n}. \label {Eq.Binomial} \end {equation} \section {Schur and Holt Congruences} The remainder of this paper contains many polynomial congruences. A statement such as \begin {equation*} a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \equiv 0 \pmod {p} \end {equation*} in the indeterminant $x$ means that $a_k \equiv 0 \pmod {p}$ for all $k$. The coefficients $a_k$ are allowed to be fractions if the denominator is not divisible by $p$. Papers by Carlitz \cite {Carlitz} and Wahab \cite {Wahab} have congruences for Legendre polynomials modulo an odd prime $p$. In particular, Carlitz cites the congruence of Schur: if $n$ is written in base~$p$ as \begin {equation} n=n_0 + n_1 p + n_2 p^2 + \cdots + n_r p^r \quad (0 \le n_i < p), \label {Eq.BaseP} \end {equation} then \begin {equation} P_n(x) \equiv P_{n_0}(x) \; (P_{n_1}(x))^p \; (P_{n_2}(x))^{p^2} \ldots (P_{n_r}(x))^{p^r} \pmod {p}. \label {Eq.Schur} \end {equation} This beautiful congruence, which is reminiscent of Lucas' theorem for binomial coefficients, is proved by Wahab \cite [Theorem 6.1] {Wahab}. The congruence implies that the divisibility of $P_n(x)$ by $p$ is completely determined by the divisibility of $P_k(x)$ by $p$ for $0 \le k < p$. We may use Fermat's little theorem to write congruence~\eqref {Eq.Schur} as \begin {equation*} P_n(x) \equiv P_{n_0}(x) \; P_{n_1}(x^p) \; P_{n_2}(x^{p^2}) \ldots P_{n_r}(x^{p^r}) \pmod {p}. \end {equation*} If we replace $x$ by an integer $s>0$, then Schur's congruence still holds and we use Fermat's little theorem to obtain a congruence without exponents: \begin {equation} P_n(s) \equiv P_{n_0}(s) \; P_{n_1}(s) \; P_{n_2}(s) \ldots P_{n_r}(s) \pmod {p}. \label {Eq.LegenProd} \end {equation} Another result mentioned by Carlitz and Wahab is due to Holt \cite {Holt}: \begin {equation} P_k(x) \equiv P_{p-k-1}(x) \pmod {p} \label {Eq.Holt} \end {equation} for $k0$ and discriminant $d \ne 0$. For specific integer $n>0$ and prime $p$, let $(n)_p = (n_i)$ denote the base $p$ representation of $n$, as in equation~\eqref {Eq.BaseP}. We begin with the case $p=2$, which cannot be handled with Legendre polynomials due to the powers of 2 in their denominators. \begin {theorem} \label {T.Base2} %-------------------------------------------------------------------------- theorem 1 If $p=2$, then $T_n \equiv b \pmod {p}$. \end {theorem} \begin {proof} In the sum in equation~\eqref {Eq.Basic}, the $k=0$ term is $b^n$; the other terms are $0 \pmod {2}$ because $\binom {2k} {k}$ is even for $k>0$. The theorem follows from $b^n \equiv b \pmod {2}$ for $n>0$. \end {proof} When $p$ is an odd prime there are four cases to consider: whether or not $p \mid b$ and whether or not $p \mid d$. We do not treat the case of $p \nmid b d$ except in the general case treated by Theorem~\ref {T.5}. The following three theorems cover the three remaining cases. The easiest case is $p$ dividing both $b$ and $d$, which we treat first. \begin {theorem} \label {T.2} %-------------------------------------------------------------------------------- theorem 2 If $p$ is an odd prime with $p \mid b$ and $p \mid d$, then $p \mid T_n$. \end {theorem} \begin {proof} Because $d=b^2-4c$, $p \mid b$ and $p \mid d$ imply $p \mid c$. Then, using equation~\eqref {Eq.Basic}, it is easy to see that $p$ divides every term of the sum. Hence, $p \mid T_n$. \end {proof} \begin {theorem} %---------------------------------------------------------------------------------------------- theorem 3 Let $p$ be an odd prime with $p \mid b$ and $p \nmid d$. Then the following are true: \\ \indent (1) if $n_i$ is odd for some $0 \le i \le r$, then $p \mid T_n$, \\ \indent (2) if $n_i$ is even and $n_i \le (p-1)/2$ for all $0 \le i \le r$, then $p \nmid T_n$, \\ \indent (3) if $p \mid T_n$, then either $n_i$ is odd or $n_i > (p-1)/2$ for some $0 \le i \le r$. \end {theorem} \begin {proof} Part 1: Using equation~\eqref {Eq.Basic}, $b$ is a factor in every term of the sum when $n$ is odd. Hence, because $p \mid b$, we obtain $p \mid T_n$ for odd $n$. By congruence~\eqref {Eq.Fundamental}, this divisibility extends to all $n$ such that $n_i$ is odd for some $0 \le i \le r$. Part 2: If $n_i$ is even for all $i$, then $n$ is even. For even $n$, the last term of equation~\eqref {Eq.Basic} is $\binom {2n} {n} c^{n/2}$; all the other terms are divisible by $p$ because those terms have a factor of $b$, which $p$ divides. Note that $d=b^2-4c$, $p \mid b$, and $p \nmid d$ imply $p \nmid c$. Because we assume $n_i \le (p-1)/2$ for all $i$, there are no carries when $n$ is added to $n$ in base $p$. Hence, by Kummer's theorem, $ p \nmid \binom {2n} {n}$. Thus, $p$ does not divide $\binom {2n} {n} c^{n/2}$ and we obtain $p \nmid T_n$. Part 3: this is just the contrapositive of part 2. \end {proof} \begin {theorem} \label {T.4} %-------------------------------------------------------------------------------- theorem 4 Let $p$ be an odd prime with $p \nmid b$ and $p \mid d$, then $p \mid T_n$ if and only if $(p+1)/2 \le n_i \le p-1$ for some $0 \le i \le r$. \end {theorem} \begin {proof} From congruence~\eqref {Eq.Fundamental}, we see that $p \mid T_n$ iff $p \mid T_{n_i}$ for some $0 \le i \le r$. Hence, we assume that $n0$. Using Theorem~\ref {T.Base2}, we conclude $p \mid T_n$ if and only if $p \mid T_1$. For odd prime $p$, the theorem follows from congruence~\eqref {Eq.Fundamental}. \end {proof} \indent For the case $a=b=c=1$, Deutsch and Sagan \cite [Conjecture 5.8] {DS} and David W. Wilson conjecture that, for $n0$, and Fermat's little theorem. \end {proof} \begin {theorem} \label {T.8} %--------------------------------------------------------------------------------- theorem 8 For odd prime $p$, \begin {equation*} T_{p-1} \equiv d^{(p-1)/2} \; P_{p-1} \bigg ( \frac {b} {\sqrt {d}} \bigg ) \equiv \bigg (\frac {d} {p} \bigg ) \pmod {p}, \end {equation*} where $ (\frac {d} {p} )$ is the Legendre symbol. \end {theorem} \begin {proof} The first congruence is equation~\eqref {Eq.Legendre}. By congruence~\eqref {Eq.Holt2} and the fact that $T_0 = 1$, we obtain $T_{p-1} \equiv d^{(p-1)/2} \; T_0 \equiv d^{(p-1)/2} \pmod {p}$. By Euler's criterion, $(\frac {d} {p} ) \equiv d^{(p-1)/2} \pmod {p}$. Hence, $T_{p-1} \equiv (\frac {d} {p} ) \pmod {p}$. \end {proof} \begin {theorem} %----------------------------------------------------------------------------------------------- theorem 9 For odd prime $p$, \begin {equation*} T_{p-2} \equiv b d^{(p-3)/2} \pmod {p}. \end {equation*} \end {theorem} \begin {proof} If $p=3$, then $T_1=b$. If $p \ge 5$ and $p \mid d$, then clearly $T_{p-2} \equiv 0 \pmod p$ by Theorems~\ref {T.2} and~\ref {T.4}. If $p \nmid d$, then the theorem follows from $T_1=b$ and congruence~\eqref {Eq.Holt2}. \end {proof} \section {Appendix} Here we prove the generalization of the Schur congruence~\eqref {Eq.Schur} and Holt congruence~\eqref {Eq.Holt} for the scaled Legendre polynomials $Q(x,d)$ defined by \eqref {Eq.Q}. In several cases, the parameter $d$ forces the proofs to be somewhat different than the ones by Holt \cite {Holt} and Wahab \cite {Wahab}. In all cases, $p$ is an odd prime and all congruences are modulo $p$. We use $Q_n$ as shorthand for the polynomial $Q_n(x,d)$. As mentioned above, $Q_n$ satisfies the recursion equation \begin {equation} n Q_n = (2n-1)x Q_{n-1} - (n-1)d Q_{n-2} \label {Eq.QRecur} \end {equation} starting with $Q_0=1$. Note that because all the denominators in $Q_n$ are powers of 2, which are relatively prime to $p$, we replace equation~\eqref {Eq.QRecur} by the congruence \begin {equation} n Q_n \equiv (2n-1)x Q_{n-1} - (n-1)d Q_{n-2}. \label {Eq.QRecurMod} \end {equation} We begin by proving four lemmas that are stated, but not proved in Wahab \cite[Lemma 6.2] {Wahab}. The first proof is almost identical to Holt's proof. \begin {lemma} \label {L.1} %-----------------------------------------------------------------------------lemma 1 If $0 \le r