\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} %\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd} \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 Unimodal Rays in the Ordinary and \\ \vskip .1in Generalized Pascal Triangles} \bigskip \vskip 1cm \large Hac\`ene Belbachir\footnote{Research supported by LAID3 Laboratory of USTHB University and by TASSILI CMEP Accord 05 MDU641b.}\\ USTHB, Faculty of Mathematics\\ P.O.~Box 32\\ El Alia, Algiers\\ Algeria\\ \href{hbelbachir@usthb.dz}{\tt hbelbachir@usthb.dz}\\ \href{hacenebelbachir@gmail.com}{\tt hacenebelbachir@gmail.com} \ \\ L\'aszl\'o Szalay\footnote{Research supported by a J\'anos Bolyai Scholarship of HAS, and by Hungarian National Foundation for Scientific Research Grant No.~T 048954 MAT, No.~T 61800 FT.} \\ Institute of Mathematics and Statistics\\ University of West Hungary\\ Erzs\'ebet utca 9\\ H-9400 Sopron\\ Hungary \\ \href{laszalay@ktk.nyme.hu}{\tt laszalay@ktk.nyme.hu}\\ \end{center} \vskip .2 in \begin{abstract} The present paper provides the solution of two problems recently posed by Bencherif, Belbachir and Szalay. For example, they conjectured that any sequence of binomial coefficients lying along a ray in Pascal's triangle is unimodal. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{theorem}{Theorem} %\newtheorem{lemma}{Lemma} %\newtheorem{claim}[theorem]{Claim} \newtheorem{cor}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{definition}{Definition} \newtheorem{question}{Question} \newtheorem{rem}[theorem]{Remark} \newtheorem{conj}{Conjecture} \section{Introduction} Let $\omega$ denote a positive integer or infinity. A real sequence $\{a_k\}_{k=0}^\omega$ is {\it unimodal} if there exists a non-negative integer $\lambda$ such that the subsequence $\{a_k\}_{k=0}^\lambda$ increases, while $\{a_k\}_{k=\lambda}^\omega$ decreases. If $\lambda=0$ then the sequence is monotone decreasing. Therefore it is also natural to consider a monotone increasing sequence as unimodal with $\lambda=\omega$, even if $\omega=\infty$. If $a_0\le a_1\le\cdots \le a_{m-1}a_{M+1}\ge a_{M+2}\ge\cdots$ then the integers $m,\dots,M$ are called the {\it modes} of the sequence. In case of $m=M$, we talk about a {\it peak}; otherwise the set of modes is called a {\it plateau}. A non-negative real sequence $\{a_k\}$ is {\it logarithmically concave} ({\it log-concave} or {\it LC} for short) if $$a_k^2\ge a_{k-1}a_{k+1}$$ for all $k\ge 1$. Unimodal and log-concave sequences occur in several branches of mathematics (see, for example \cite{Br,S}). Our main interest is to examine combinatorial sequences connected to Pascal's triangle and its generalizations. The first result dealing with unimodality of the elements of the Pascal triangle is due to Tanny and Zuker \cite{TZ1}, who showed that the sequence of the terms $n-k \choose k$ $(k=0,\dots,\left\lfloor \frac{n}{2}\right\rfloor)$ is unimodal. In fact, the LC property of the sequence formed by the binomial coefficients $n-k \choose k$ was proved, and this implies unimodality by Theorem~\ref{t:LCUM}. They also investigated the unimodality of $\left\{{n-\alpha k \choose k}\right\}$ in \cite{TZ1fel,TZ2}. Benoumhani \cite{B} justified the unimodality of the sequence $\left\{\frac{n}{n-k}{n-k \choose k}\right\}$ connected to Lucas numbers. Recently, Belbachir and Bencherif \cite{BB2} proved that the elements $2^{n-2k}{n-k \choose k}$ and $2^{n-2k}\frac{n}{n-k}{n-k \choose k}$ linked to the Pell sequence and its companion sequence, respectively, provide unimodal sequences. In all the aforesaid cases the authors descibe the peaks and the plateaus with two elements. Incidentally, the paper \cite{BBSz} generalizes certain results on unimodality of sequences mentioned above. One of the purposes of this work is to prove that any ray crossing Pascal's triangle hits elements of an unimodal sequence (Theorem~\ref{t:ray} and Corollary \ref{cor0}). Further, we will show that unimodality appears when we consider the generalized Pascal triangle linked to the homogeneous linear recurrence $\{T_n\}$ of order $s$ given by the recurrence relation \begin{equation}\label{T} T_n=T_{n-1}+\cdots+T_{n-s},\quad n\ge s \end{equation} and by the initial values \begin{equation}\label{Tini} T_{0}=\cdots=T_{s-2}=0,\;T_{s-1}=1 \end{equation} (Theorem~\ref{t:raygen} and Corollary \ref{cor1}). Questions of a similar kind were posed in the paper of Belbachir, Bencherif and Szalay \cite{BBSz}. For the proofs we will need the following two theorems. \begin{theorem} \label{t:LCUM} A log-concave sequence $\{a_k\}$ with no internal zeros is also unimodal. \end{theorem} See, for instance, \cite{Br}. \begin{theorem} \label{t:ordconv} The ordinary convolution of two log-concave sequences preserves the LC property. More precisely, if both $\{a_n\}$ and $\{b_n\}$ are log-concave, then so is $\{c_n\}$ with $$ c_n=\sum_{i=0}^na_ib_{n-i}\quad\quad (n=0,1,\dots). $$ \end{theorem} See, for instance, \cite{WY}. \section{Rays in Pascal's triangle} Let $u\ge0$ and $v$ denote integers, and as usual let \begin{equation}\label{binplus} {u\choose v}=\left\{% \begin{array}{ll} \frac{u!}{v!(u-v)!}, & \hbox{if $0\le v\le u$;} \\ 0, & \hbox{otherwise.} \\ \end{array}% \right. \end{equation} The main advantage of such an interpretation of binomial coefficients is, for example, that one can omit the use of exact limits in sums like $\sum_{i=0}^u{u\choose i}$ by simply writing $\sum_i{u\choose i}$ instead. In the sequel, for the sake of convenience, we exploit this kind of allowance. As a demonstration, we state Vandermonde's identity here, without proof. \begin{lemma}\label{l1} For arbitrary integers $u\ge0$, $k\ge0$ and $v$ we have $$ {u+k\choose v}=\sum_i{k\choose i}{u\choose v-i}. $$ \end{lemma} \noindent For the set of non-zero binomial coefficients we use the phrase {\it Pascal's triangle}. Since any row $R^{(u)}$ ($u\ge0$) of the Pascal triangle is the convolution powers of the log-concave constant sequences $\{1\}$ and $\{1\}$, it follows that $R^{(u)}$ is a log-concave sequence by Theorem \ref{t:ordconv}, even if we extend $R^{(u)}$ by (\ref{binplus}). (The log-concavity of a row in the Pascal triangle also follows from the direct application of the definition of LC property.) Now we are ready to prove \begin{theorem}\label{t:ray} The sequence of binomial coefficients located along a ray is log-concave. \end{theorem} By Theorem {\ref{t:LCUM}}, we immediately obtain \begin{cor}\label{cor0} The sequence of binomial coefficients located along a ray is unimodal. \end{cor} \bigskip {\it Proof of Theorem {\ref{t:ray}}.} Since the sequence of zeros is trivially log-concave, it is sufficient to prove the case when the ray passes through at least one binomial coefficient in the Pascal triangle. Let ${u_0\choose v_0}$ denote such a coefficient. Thus $0\le v_0\le u_0$, and with the integers $\alpha$ and $\beta$ satisfying $\alpha^2+\beta^2>0$ let us consider the sequence $\{x_k\}$ given by \begin{equation} x_k={u_0+\alpha k\choose v_0+\beta k}, \end{equation} where the integer $k$ varies over all cases when $u_0+\alpha k\ge v_0+\beta k\ge0$. Since the choice $k=0$ is feasible, the sequence $\{x_k\}$ contains at least one positive element. Without loss of generality we may suppose that $\gcd(\alpha,\beta)=1$. If $\alpha=0$ then $\{x_k\}=\left\{{u_0\choose v_0\pm k}\right\}$ is the log-concave row $R^{(u_0)}$ of binomial coefficients. Similarly, if $\beta=0$ then one can readily show that the terms $x_k={u_0\pm k\choose v_0}$ provide log-concave sequence. To deduce this statement, it suffices to show by recalling the definition of log-concavity, that \begin{equation}\label{insx} {u_0+1\choose v_0}{u_0-1\choose v_0}\le{u_0\choose v_0}^2, \quad\quad\text{if}\;\;0\le v_0\le u_0-1, \end{equation} since the direction of a ray is reversible. By simply extracting the binomial coefficients, we can check that the above inequality is equivalent to $u_0-v_0\le u_0$. Moreover, there is no restriction in assuming that $\alpha$ and $\beta$ are positive because of the symmetry ${n\choose k}={n\choose n-k}$ of Pascal's triangle (or generally, by (\ref{binplus}), the symmetry of binomial coefficients). Suppose now, that ${u\choose v}$ (where $0\le v\le u$) is the element of $\{x_k\}$ for which $0\le u=u_0+\alpha k$ is minimum. Then the sequence $\{\bar{x}_k\}=\left\{{u+\alpha k\choose v+\beta k}\right\}_{k\ge0}$ contains $\{x_k\}$ as a subsequence. By Lemma \ref{l1}, it is clear that \begin{equation}\label{fo} \bar{x}_k={u+\alpha k\choose v+\beta k}=\sum_i{k\choose i}{u+(\alpha-1) k\choose v+\beta k-i}. %=\sum_i{k\choose i}{u+(\alpha-1) k\choose u-v+(\alpha-\beta-1)k+i}. \end{equation} Since the terms $a_i={k\choose i}$, and $b_i={u+(\alpha-1) k\choose v+\beta k-i}$ are from the row $R^{(k)}$ and $R^{(u+(\alpha-1)k)}$ of binomial coefficients, respectively, they clearly form log-concave sequences. Thus $\{\bar{x}_k\}$ is also log-concave. Indeed, $k\ge0$, and by $u\ge0$ and $\alpha\ge1$ we have $u+(\alpha-1)k\ge0$, so the two sequences framing the convolution really exist. Then the proof of Theorem \ref{t:ray} is complete. $\diamond$ \section{Generalized Pascal triangle and sequences $T_n$} The elements ${n\choose k}_s$ of the generalized Pascal triangle have the following combinatorial interpretation. The term ${n\choose k}_s$ assigns the number of different ways of distributing $k$ uniform objects among $n$ boxes, where each box may contain at most $s$ objects. Clearly, $0\le k\le sn$. In other words, ${n\choose k}_s=\left|\left\{ f:\{0,\dots,n-1\}\rightarrow \{0,\dots,s\}\mid\sum_{i=0}^{n-1}f(i)=k\right\}\right|$. For instance, if $s=2$ we obtain the triangle \begin{center} \begin{tabular}{ccccccc} & & & 1 & & & \\ & & 1 & 1 & 1 & & \\ & 1 & 2 & 3 & 2 & 1 & \\ 1 & 3 & 6 & 7 & 6 & 3 & 1 \ ,\\ & & & \vdots & & & \\ \end{tabular} \end{center} where ${n\choose k}_2={n-1\choose k-2}_2+{n-1\choose k-1}_2+{n-1\choose k}_2$, supposing non-negative $u$ in ${u\choose v}_2$ having the value zero if $v<0$ or $2u