\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://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Asymptotics for Lacunary Sums of Binomial \\ \vskip .1in Coefficients and a Card Problem with Ranks } \vskip 1cm \large Tam\'as Lengyel\\ Mathematics Department\\ Occidental College\\ 1600 Campus Road\\ Los Angeles, CA 90041\\ USA\\ \href{mailto:lengyel@oxy.edu}{\tt lengyel@oxy.edu} \end{center} \vskip .2 in \def\k{l} \begin{abstract} We find asymptotics for lacunary sums of binomial coefficients. As an application we determine the exact and approximate probability that the first card has the uniquely highest rank among the top $\k$ cards of a standard card deck. \end{abstract} %\newtheorem{theorem}{Theorem} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{conjecture}[theorem]{Conjecture} \def\citep#1#2{\cite[#1]{#2}} \def\forallx{\, \text{ for all }} \def\vag{\smallskip\hrule\smallskip} \newenvironment{remark*}[1]{\bf{Remark.\,\,} \rm {#1} } { } \def\hockeystick{hockey stick} \def\k{i} \def\K{k} \def\i{l} \def\mm{m_1} %%%%%%%%%%%%%%%%%% \def\eddig{8} \def\innen{9} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\parindent 0pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} % In card games, we often pick the first $\k$ cards from the top of a standard deck and check the ranks of these cards as they show up. The kings have the highest rank, 13, while the aces have the lowest, 1. What are the chances, $p_\k$, that the first card has the uniquely highest rank among these $\k$ cards? One expects this number to be slightly less than $1/\k$ for small values of $\k$. We will obtain some asymptotics for this probability in the generalized case in which there are $m$ denominations (of face values $1,~2,~\dots,~m$) in each of $\K$ suits, i.e., $m=13$ and $\K=4$ for the standard deck. We prove \def\kitt{{1/4}} \newtheorem{theorem}{Theorem} \begin{theorem} \label{th:elso} Let $\k, \K$ and $m$ be positive integers and $p_\k$ as defined above. Then \begin{equation} \label{eq:as} p_\k\approx \frac{1}{\k}-\frac{1}{2 m} \left(1-\frac{1}{\K}\right), \end{equation} for $2\le \k\le m^\kitt$ as $m\to \infty$. \end{theorem} We can rephrase Theorem~\ref{th:elso} and obtain Theorem~\ref{th:masodik} which is of general interest since it concerns the $\K$-sected version of the so-called upper summation \citep{p.~174}{GrKnPa} (sometimes also referred to as the \hockeystick\ pattern, though apparently, there is some confusion regarding this naming convention). \begin{theorem} \label{th:masodik} Let $\k, \K$ and $m$ be positive integers. We have that \begin{equation} \label{eq:binom} \sum_{\i=1}^m {\K(\i-1)\choose{\k-1}}\sim {\K m\choose \k}\frac{1}{\K} \left(1-\frac{\k}{2m}\left(1-\frac{1}{\K}\right)\right) \end{equation} for $2\le \k\le m^\kitt$ as $m\to\infty$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Some particular lacunary sums of this type have combinatorial interpretations (cf. Table 1), and they appear in Sloane's On-Line Encyclopedia of Integer Sequences \cite {Sloane}. \begin {table}[H] \begin {center} \label {Ta1} {\footnotesize \begin {tabular} {|r|r|c|l|} \hline & & & \\[-5pt] $\K$ & $\k$ & A-number & Comments\\ & & & \\[-5pt] \hline 2 & 3 & \seqnum {A002412} & hexagonal pyramidal numbers, or greengrocer's numbers \\ 2 & 4 & \seqnum {A112742} & second derivative of the $n$-th Chebyshev polynomial\\ &&& (of the first kind) evaluated at $x=1$\\ 3 & 4 & \seqnum {A116689} & partial sums of dodecahedral numbers\\ \hline \end {tabular} } \caption {Lacunary sums of binomial coefficients} \end {center} \end {table} We can extend Theorem~\ref{th:masodik} for other $\K$-sections using simple identities for binomial coefficients. \begin{theorem} \label{th:harmadik} Let $\k, \K$ and $m$ be positive integers and $j$ be an integer so that $0\le j<\min\{\k,\K\}$. We have that \begin{equation} \label{eq:binom2} \sum_{\i=1}^m {\K(\i-1) +j\choose{\k-1}}\sim {\K m+j\choose \k}\frac{1}{\K} \left(1-\frac{\k}{2(m+\frac{j}{\K})}\left(1-\frac{1}{\K}\right)\right) \end{equation} for $2\le \k\le m^\kitt$ as $m\to\infty$. \end{theorem} The approximation (\ref{eq:binom}) (and subsequently, (\ref{eq:binom2})) can be improved by involving more terms in the last factor as it is indicated immediately after (\ref{eq:reszlet}) for approximating $p_\k$. Note that the sum in (\ref{eq:binom}) has a closed form by standard binomial summation if $\K=1$, and it corresponds to the upper summation identity. In this case, equality holds in (\ref{eq:binom}) for all positive integers $\k$ and $m$. The same applies to (\ref{eq:binom2}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} The simplest version of the card selection problem is proposed in \citep{Example~2.3.3}{ML} with the standard deck and $\k=2$: ``Two cards are drawn from a poker deck without replacement. What is the probability that the second is higher in rank than the first?" We use the notation \[ \begin{array}{ll} A_\k&=\text{the rank of first card exceeds that of the other $\k-1$ cards, so}\\ A_2&=\text{the rank of first card exceeds that of the second card,}\\ B&=\text{the rank of second card exceeds that of the first card,}\\ C&=\text{the first and second cards have the same rank}. \end{array} \] Clearly, $P(A_2)=P(B)$, by symmetry, and $P(C)=\frac{3}{51}$ which yields $P(A_2)=\frac{24}{51}=\frac{1}{2}-\frac{3}{102}\approx 0.4706$, while the approximation (\ref{eq:as}) yields $p_2\approx \frac{1}{2}-\frac{1}{26}\left(1-\frac{1}{4}\right)\approx 0.4712$. \def\A{D} By using conditional probabilities, we get that in general, \begin{equation} \label{eq:PA} \begin{array}{ll} p_\k=P(A_\k)&=\sum_{\i=1}^m P(A_\k\mid \A_\i) P(\A_\i)=\sum_{\i=1}^m \frac{{\K(\i-1)\choose \k-1}}{{\K m-1\choose \k-1}} \frac{\K}{\K m} \\ &=\frac{\K}{\k}\frac{1}{{\K m\choose \k}} \sum_{\i=1}^m {\K(\i-1)\choose \k-1}, \end{array} \end{equation} with $\A_\i$ being the event that the first card is of face value $\i=1,2,\dots,m$. Clearly, $p_1=1$ and $p_{\K(m-1)+1}=1/{\K m\choose \K}$, since in the latter case, the first card and the last $\K-1$ cards in the full deck of $\K m$ cards are of the highest rank. Easy calculation shows that $p_2=\frac{\K(m-1)}{2(\K m-1)}$ but $p_\k$ looks less and less manageable as $\k$ gets large. Also, it is obvious that $p_\k=1/\k$ for $\K=1$. We applied symbolic summation techniques to rewrite (\ref{eq:binom}), (\ref{eq:binom2}) and (\ref{eq:PA}) but did not succeed in obtaining useful closed forms. Note, however, that we can derive the generating function of the last sum in (\ref{eq:PA}) in the form of \[g(x)=\sum_{\k=1}^{\K(m-1)+1} p_\k \frac{\k}{\K}{{\K m\choose \k}} x^\k=\sum_{\k=1}^{\K(m-1)+1} \sum_{\i=1}^m {\K(\i-1)\choose{\k-1}} x^\k\] through the generating function in two variables \[ \begin{array}{ll} f(x,y)&=\sum_{\k=1}^{\K(m-1)+1} \sum_{\i=1}^m {\K(\i-1)\choose \k-1} x^\k y^\i =\sum_{\i=1}^m y^\i \sum_{\k=1}^{\K(\i-1)+1} {\K(\i-1)\choose \k-1} x^\k \\ &=\sum_{\i=1}^m y^\i x(1+x)^{\K(\i-1)}=x y\frac{1-\left(y(1+x)^\K \right)^m}{1-y(1+x)^\K}. \end{array} \] In fact, it follows that $g(x)=f(x,1)=x \frac{1-(1+x)^{\K m}}{1-(1+x)^\K}$. However, this does not seem to help with the asymptotics. \def\n{m} \section {Proof of Theorem~\ref{th:elso}} % Clearly, $p_1=1$, and it is easy to see that $p_\k=\frac{1}{\k}-\frac{1}{2m}(1-\frac{1}{\K})+ \frac{\left( \k-1 \right) \,\left( \K^2 -6\, \K +5 \right) }{12\,\K^2 m^2}+O(\frac{1}{m^3})$ for $2\le \k \le \eddig$ as $m\to\infty$, in agreement with (\ref{eq:as}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\harom{3} \def\egy{1} \def\ketto{2} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% By standard asymptotical expansion of the binomial coefficients, we have that % \begin{equation} \label{eq:fact} {n\choose k}= \frac{n^k}{k!} \left(1-\frac{{k \choose 2}}{n}+ \frac{(3k-1){k\choose 3}}{4n^2}+ O\left(\frac{k^6}{n^3}\right) \right), \end{equation} which is useful when $k= O\left( n^{1/2-\epsilon }\right)$ with any small positive $\epsilon$. We will use the inequality \begin{equation} \label{eq:small} {n\choose k}\le \frac{n^k}{k!}, \end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% which holds for every $k, 0\le k\le n$, in the second part of the estimation (\ref{eq:pk}). %%%%%%%%%%%%%%%%%%%%%%%%%%% On the other hand, %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{equation} \label{eq:Bern} \begin{array}{ll} \sum_{\i=1}^\n (\i-1)^\k&=\frac{1}{\k+1}\sum_{\i=0}^{\k} {\k+1\choose \i} B_\i \n^{\k+1-\i}\\ &= \frac{1}{\k+1}\n^{\k+1}-\frac{1}{2}\n^\k+\frac{\k}{12} \n^{\k-1} + O\left(\k^2 \n^{\k-2} \right) \end{array} \end{equation} with $\k=o\left( \n\right)$ by using the Bernoulli numbers, $B_\i$ \citep{Section 6.5}{GrKnPa}; for example, $ B_0=1, B_1=-\frac{1}{2} ,B_2=\frac{1}{6},B_3=0, B_4=- \frac{1}{30}, B_5=0,$ and $B_6=\frac{1}{42}$. We note that an alternative approach for approximating sums of powers is outlined in \cite{BT} based on an observation of Bernoulli which is related to the Faulhaber polynomials \cite{edwards} \begin{equation} \label{eq:BT} \sum_{\i=1}^m (\i-1)^\k=\frac{\mm^{\k+1}}{\k+1}\left(1-\frac{{\k+1\choose 2}}{12 \mm^2}+\frac{7 {\k+1\choose 4}}{240 \mm^4}-\dots\right) %%% \text{ with } \mm=m-\frac{1}{2}. \end{equation} %%% For an application of this technique see \cite{tsaban}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Note that while in the expansion (\ref{eq:Bern}) the fourth term vanishes since $B_3=0$, in the alternative approach the second term vanishes already. This fact might help in getting the asymptotic evaluations below a little faster, although by somewhat more complicated expansions. This approach can be easily tested by some software with symbolic calculation capabilities. We achieved this by using the {\it Mathematica} function {\tt FullSimplify} with the assumption that the exponents in the terms of the form $(m-\frac{1}{2})^\k$ are positive integers. In fact, to get the approximation (\ref{eq:as}), we need only \[ \frac{1}{m^\k} \left(1+\frac{{\k \choose 2}}{\K m}\right) \left(\frac{(m-\frac{1}{2})^\k}{\k} -\frac{{\k-1\choose 2}}{\K} \frac{(m-\frac{1}{2})^{\k-1}}{\k-1}\right),\] while our main approach requires an extra term from the expansion (\ref{eq:Bern}) (cf. (\ref{eq:vege})) \[\frac{1}{m^\k} \left(1+\frac{{\k \choose 2}}{\K m}\right) \left(m^\k\left(\frac{1}{\k}-\frac{1}{2m}\right) -\frac{{\k-1\choose 2}}{\K} m^{\k-1} \frac{1}{\k-1}\right)\] to obtain (\ref{eq:reszlet}). In order to determine the next term (\ref{eq:2nd}) of the approximation, we need 4 and 6 terms of the expansions (\ref{eq:BT}) and (\ref{eq:Bern}), respectively. % We note, however, that in both approaches, every other term vanishes after the initial terms. The good news is that the dominant terms in the sum (\ref{eq:PA}) have large values of $\i$ in the binomial coefficients for which we can use the asymptotics given in (\ref{eq:fact}). This fact will make the approximation surprisingly effective even for fairly large values of $\k$. \def\nev{\left(1-\frac{{\k\choose 2}}{\K m}+O\left(\frac{\k^3}{m^2} \right)\right)} \def\szam{ 1+\frac{{\k\choose 2}}{\K m}+O\left(\frac{\k^3}{m^2} \right) } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\kit{6} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\szorzo{{\frac{\k!}{(\K m)^\k}} { \left(1+\frac{{\k \choose 2}}{\K m}+ \frac{(3\k-2){\k+1\choose 3}}{4(\K m)^2}+O\left(\frac{\k^\kit}{(\K m)^3}\right) \right) }} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\xxx{\ \ } \def\xx{\xxx}%\xxx}%\xxx} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\kittt{{8/3}} \def\kitte{{3/8}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\szaml{ 1+\frac{{\k \choose 2}}{\K m}+ \frac{(3\k-2){\k+1\choose 3}}{4(\K m)^2}+O\left(\frac{\k^\kit}{(\K m)^3}\right) } %% \def\szamlk{ 1+\frac{{\k \choose 2}}{\K m}+ \frac{(3\k-2){\k+1\choose 3}}{4(\K m)^2} } %% %% \def\A{A} \def\hiba{O\left(\frac{1}{\k m^3}\right)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\k$ be any integer between \innen\ and the sufficiently large $m^\kitt$, and $a(\k)= \lceil \frac{\k^ \kittt }{\K}\rceil +1 $. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%% !!!!!!!!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This choice guarantees \begin{equation} \label{eq:ak} \left(\frac{a(\k)}{m}\right)^\k=O\left(\left(\frac{1}{\K m^{1/3 }}\right)^\k\right)=O\left(\frac{1}{m^3}\right). \end{equation} %%%%%%%%%%%% Note that as $\n\to \infty$, formulas (\ref{eq:Bern}) and (\ref{eq:ak}) yield the asymptotics \begin{equation} \label{eq:eleje} \sum_{\i=1}^{a(\k)-1} (\i-1)^{\k-1}=a(\k)^{\k} \left(\frac{1}{\k}-\frac{1}{2 a(\k)}+\frac{\k-1}{12a(\k)^2}+O\left(\frac{\k^2}{a(\k)^3}\right) \right) \end{equation} %%%%%%%%%%%% and %%%%%%%%%%%% \begin{equation} \label{eq:vege} \begin{array}{ll} \sum_{\i=a(\k)}^\n (\i-1)^{\k-1}&=\sum_{\i=1}^\n (\i-1)^{\k-1}-\sum_{\i=1}^{a(\k)-1} (\i-1)^{\k-1}\\ &=\n^{\k} \left(\frac{1}{\k}-\frac{1}{2\n}+ \frac{\k-1}{12\n^2}+O\left(\frac{\k^2}{\n^3}\right) \right)+\n^\k \left(\frac{a(\k)}{\n}\right)^\k O\left(\frac{1}{\k}\right)\\ &=\n^{\k} \left(\frac{1}{\k}-\frac{1}{2\n}+ \frac{\k-1}{12\n^2}+O\left(\frac{\k^2}{\n^3}\right) \right)+\n^\k O\left(\frac{1}{\k m^3}\right). \end{array} \end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The identity (\ref{eq:fact}) implies that \begin{equation} \label{eq:denom} \begin{array}{lll} &{{\K m \choose \k}}&= {\frac{(\K m)^\k}{\k!}\left(1-\frac{{\k \choose 2}}{\K m}+ \frac{(3\k-1){\k\choose 3}}{4(\K m)^2}+O\left(\frac{\k^\kit}{(\K m)^3}\right) \right)}, \\ &\frac{1}{{\K m \choose \k}}&= \szorzo. \end{array} \end{equation} %% %% %% According to (\ref{eq:PA}), (\ref{eq:fact}), (\ref{eq:small}), (\ref{eq:ak}), (\ref{eq:eleje}) and % (\ref{eq:denom}), and with $\A=\frac{\K}{\k}\frac{1}{{\K m\choose \k}}$, we get that \begin{equation} \label{eq:pk} \begin{array}{ll} p_\k&=\A \sum_{\i=1}^m {\K(\i-1)\choose \k-1}\\ %\\ &= \A \left( \sum_{\i=a(\k)}^m {\K(\i-1)\choose \k-1}+\frac{\K^{\k-1}}{\k!} O(a(\k)^\k ) \right)\\ &=\frac{\K}{\k} \szorzo \\ & \times \sum_{\i=a(\k)}^m \frac{\K^{\k-1}(\i-1)^{\k-1}}{(\k-1)!}\big(1-\frac{{\k-1\choose 2}}{\K (\i-1)}+\frac{(3\k - 4){\k-1\choose 3}}{4 (\K (\i-1))^2} %\\ & + O\left(\frac{\k^\kit}{(\i-1)^3} \right)\big)+\hiba, %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{array} \end{equation} for $a(\k)\le \i$ implies that $\k\le \left(\K(\i-1)\right)^ \kitte$, and thus, we can use (\ref{eq:fact}) in the last part of (\ref{eq:pk}). % % % Now by (\ref{eq:vege}), we derive that \[ \begin{array}{ll} p_\k %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% &=\frac{\K}{\k} \szorzo \frac{\K^{\k-1}}{(\k-1)!} \\ & \xxx \times \big( \left( \frac{1}{\k}m^{\k}-\frac{1}{2}m^{\k-1} +\frac{\k-1}{12}m^{\k-2} \right)- \frac{{\k-1\choose 2}}{\K}\left(\frac{1}{\k-1}m^{\k-1}-\frac{1}{2}m^{\k-2} +\frac{\k-2}{12}m^{\k-3} \right) \\ & \xx + \frac{(3\k - 4){\k-1\choose 3}}{4\K^2} \left( \frac{1}{\k-2}m^{\k-2}-\frac{1}{2}m^{\k-3} +\frac{\k-3}{12}m^{\k-4} \right)\big) % % +O\left(\frac{\k^5} {m^3}\right) +\hiba \end{array} \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% which can be rewritten as %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{equation} \label{eq:reszlet} \begin{array}{ll} &\left(\szamlk\right) \!\!\Big( \left( \frac{1}{\k}-\frac{1}{2m}+\frac{\k-1}{12m^2}\right) - \frac{{\k- 1\choose 2}}{\K} \left( \frac{1}{(\k-1)m} -\frac{1}{2m^2} %%%%%%%%%%%%%%%%%%%%%%%%%% \right) \\ & + \frac{(3\k - 4){\k-1\choose 3}}{4\K^2} \left( \frac{1}{(\k-2)m^{2}} -\frac{1}{2m^{3}} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \right) \Big) + O\left(\frac{\k^5} {m^3}\right) \\ &=\frac{1}{\k}-\frac{1}{2m} \left(1-\frac{1}{\K}\right)+ O\left(\frac{\k} {m^2}\right). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{array} \end{equation} \qed\\ %\medskip The error term in (\ref{eq:reszlet}) can be further determined to yield \begin{equation} \label{eq:2nd} \frac{\left( \k-1 \right) \,\left( \K^2 -6\, \K +5 \right) }{12\,\K^2 m^2}+O(\frac{1}{m^3}) \end{equation} as \hbox{$m\to \infty$} and $\k$ is kept fixed. With more involved calculations we find that the next error term is $\frac{\left( \k-1 \right) \, \left( \K-1 \right)\left( 3\left(\K-3\right)\, \k -4\, \K+8\right) }{24\,\K^3 m^3}+O(\frac{1}{m^4})$ which explains why the previous approximation becomes even better if $\K=3$ and $m$ is sufficiently large. %%%%%%%%%%%%%%%%% Note that if $\K=1$ then the second term of (\ref{eq:as}) and the above mentioned two terms vanish as one might expect since $p_\k=1/\k$ in this case. Numerical calculation and plotting $p_\k$ against $\k$ confirms that the approximation (\ref{eq:as}) is valid for a much larger set of values $\k$. (Of course, this observation is of no surprise as in the above proof we dealt with the bounds on $\k$ quite generously. We extend the range of values of $\k$ in the next section.) For example, in the case of the standard deck, we get that $p_\k\approx \frac{1}{\k}-0.029$, in agreement with the fact that second term in (\ref{eq:as}) does not depend on $\k$, and it seems to be a fairly precise over-estimation for any $2\le \k\le 22$. In general, however, numerical experimentation also suggests that the approximation (\ref{eq:as}) needs correcting terms when $\k$ grows. \section{Extending the range} \label{sec:3} The proof presented in the previous section can be improved to work for a larger set of values of $\k$; thus, we can extend the validity of Theorems~\ref{th:elso}-\ref{th:harmadik}. % In fact, let $\k$ be any integer between $9/(1-\epsilon)$ and the sufficiently large $m^{1/3}$, and $a(\k)= \lceil \frac{\k^ {2+\epsilon} }{\K}\rceil +1$ with any small positive $\epsilon$. % We note that $a(\k)\le \i$ implies that $\k\le (\K (\i-1))^{\frac{1}{2+\epsilon}}$; thus, we can use the approximation (\ref{eq:fact}) for binomial coefficients. We also need $9/(1-\epsilon)\le k$ to guarantee (\ref{eq:ak}). %%%% After streamlining the steps outlined in (\ref{eq:eleje})-(\ref{eq:reszlet}), we obtain a complete proof. First, we observe that \[ \begin{array}{lll} &{{\K m \choose \k}}&= {\frac{(\K m)^\k}{\k!}\left(1-\frac{{\k \choose 2}}{\K m}+ O\left(\frac{\k^4}{(\K m)^2}\right) \right)}, \\ &\frac{1}{{\K m \choose \k}}&= \frac{\k!}{(\K m)^\k} { \left(1+\frac{{\k \choose 2}}{\K m}+ O\left(\frac{\k^4}{m^2}\right) \right) }. \end{array} \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% It follows that \[ \begin{array}{ll} p_\k&=\A \sum_{\i=1}^m {\K(\i-1)\choose \k-1}\\ %\\ &= \A \left( \sum_{\i=a(\k)}^m {\K(\i-1)\choose \k-1}+\frac{\K^{\k-1}}{\k!} O(a(\k)^\k ) \right)\\ &=\frac{\K}{\k} \frac{\k!}{(\K m)^\k} { \left(1+\frac{{\k \choose 2}}{\K m}+ O\left(\frac{\k^4}{m^2}\right) \right) } \\ & \times \sum_{\i=a(\k)}^m \frac{\K^{\k-1}(\i-1)^{\k-1}}{(\k-1)!}\big(1-\frac{{\k-1\choose 2}}{\K (\i-1)} %\\ & + O\left(\frac{\k^4}{(\i-1)^2} \right)\big)+\hiba, %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{array} \] therefore, \[ \begin{array}{ll} p_\k %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% &=\frac{\K}{\k} \frac{\k!}{(\K m)^\k} { \left(1+\frac{{\k \choose 2}}{\K m}+ O\left(\frac{\k^4}{m^2}\right) \right) } \frac{\K^{\k-1}}{(\k-1)!} \\ & \xxx \times \big( \left( \frac{1}{\k}m^{\k}-\frac{1}{2}m^{\k-1} +\frac{\k-1}{12}m^{\k-2} \right)- \frac{{\k-1\choose 2}}{\K}\left(\frac{1}{\k-1}m^{\k-1}-\frac{1}{2}m^{\k-2}\right) \\ & \xx +O(\k^4)\, \frac{1}{\k-2}m^{\k-2}\big) % % +O\left(\frac{\k^5} {m^3}\right) +\hiba. \end{array} \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This can be rewritten as %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \[ \begin{array}{ll} \left(1+\frac{{\k \choose 2}}{\K m} \right) \!\!\Big( \left( \frac{1}{\k}-\frac{1}{2m}\right) - \frac{{\k- 1\choose 2}}{\K} \frac{1}{(\k-1)m} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Big) + O\left(\frac{\k^3} {m^2}\right)\\ =\frac{1}{\k}-\frac{1}{2m} \left(1-\frac{1}{\K}\right)+ O\left(\frac{\k^3} {m^2}\right). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{array} \] \qed\\ By including more correcting terms, one might be able to extend the range for $\k$ to $m^{1/2-\epsilon}$ with any positive $\epsilon$. %%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Acknowledgments} % The author wishes to thank the referee and Gregory Tollisen for making helpful suggestions and comments that improved the presentation of this paper. % \nocite{*} \bibliographystyle{plain} \begin {thebibliography} {9} \bibitem{BT} {B.~L.~Burrows and R.~F.~Talbot}, {Sums of powers of integers}, \emph{Amer. Math. Monthly} \textbf{91} {(1984)}, {394--403.} \bibitem{edwards} {A.~W.~F.~Edwards}, {A quick route to sums of powers}, \emph{Amer. Math. Monthly} \textbf{93} {(1986)}, {451--455.} \bibitem {GrKnPa} R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik, \emph {Concrete Mathematics, A foundation for computer science}, Addison-Wesley, Reading, MA, 1994, 2nd edition. %\bibitem{GrKnPa}{Graham,~R., Knuth,~D., and Patashnik,~O. Concrete Mathematics, A foundation for computer science. Addison-Wesley, Reading, MA, 1989.} \bibitem{ML} {M.~Larsen and M.~Marx}, \emph{An Introduction to Mathematical Statistics and Its Applications}, Prentice Hall, Upper Saddle River, NJ, 2006, 4th edition. \bibitem {Sloane} N.~J.~A.~Sloane, {\em \htmladdnormallink {The On-Line Encyclopedia of Integer Sequences}{http://www.research.att.com/~njas/sequences}}, published electronically at \href{http://www.research.att.com/~njas/sequence}{\tt http://www.research.att.com/$\sim$njas/sequences}. \bibitem{tsaban} {B.~Tsaban}, {Bernoulli numbers and the probability of a birthday surprise}, \emph {Discrete Appl. Math.} \textbf {127} {(2003)}, {657--663.} \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 05A16, 11B68. \noindent \emph {Keywords:} lacunary sum, asymptotic enumeration, Bernoulli numbers. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum {A002412}, \seqnum {A112742}, and \seqnum {A116689}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 14 2007; revised version received July 2 2007. Published in {\it Journal of Integer Sequences}, July 4 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}