\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}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Expectations of Family Sizes Subject to\\ 
\vskip .08 in
Minimum Numbers of Each Gender}
\vskip 1cm
\large
Martin Griffiths\\
Mathematical Institute\\
University of Oxford\\
Oxford OX1 3LB\\
United Kingdom\\
\href{mailto:martin.griffiths@maths.ox.ac.uk}{\tt martin.griffiths@maths.ox.ac.uk} \\
\ \\
Alexander Bramham\\
Wadham College\\
University of Oxford\\
Oxford OX1 3PN\\
United Kingdom\\
\href{mailto:alexander.bramham@wadh.ox.ac.uk}{\tt alexander.bramham@wadh.ox.ac.uk}
\end{center}

\vskip .2 in

\begin{abstract}
We consider the infinite families of sequences that arise from a
scenario involving the expected number of children born to a married
couple when certain conditions are placed on the minimum number of each
gender.  We obtain both exact and asymptotic formulas for these
expectations, and go on to consider the long-term behavior of sequences
derived from them.  For the situations studied here, it is shown that
the long-term behavior of each of the resulting sequences always falls
into one of two distinct categories.
\end{abstract}

\section{Introduction}
 Suppose that a married couple plan to keep having children until the first instance at which they have at least one boy and one girl.  Assuming that boys and girls are equally likely to be born, and excluding the possibility 
of multiple births, it is a straightforward calculation to show that that the expected number of children in such a family is 3.  In \cite{griffiths2} we considered a generalization of this scenario, and derived an expression for the expected number of children our couple would need to have in order that their family contains at least $n$ boys and $n$ girls.

 In this article we generalize things yet further by studying the considerably more complicated scenario in which the parents keep having children until the first instance at which they have at least $m$ boys and $n$ girls.  It is assumed throughout that only one child is born at a time (no twins, triplets, and so on) and that on the birth of each child we have $\mathbb{P}[\text{boy}]=\mathbb{P}[\text{girl}]=\frac{1}{2}$.  Under these conditions, we obtain expressions for the expected number of children that would result.

 Our expressions give rise to infinite families of integer sequences, and we consider here the contrasting long-term behavior of these sequences under various different scenarios.  Indeed, the following definitions enable us to categorize these behaviors:
\begin{definition}
 A sequence of integers $\left(x_n\right)_{n\geq1}$ is termed \textit{linear} if there exists $a,b\in\mathbb{Z}$ such that $x_n=an+b$ for all $n\in \mathbb{N}$.
\end{definition}
\begin{definition}
 A sequence of integers $\left(y_n\right)_{n\geq1}$ is termed \textit{eventually-linear} if there exists some $N\in\mathbb{N}$ and $a,b\in\mathbb{Z}$ such that $y_n=an+b$ for all $n\geq N$.
\end{definition}
\begin{definition}\label{def2}
 An increasing sequence of integers $\left(z_n\right)_{n\geq1}$ is termed \textit{quasi-linear} if it is not eventually-linear but, for any $n\in\mathbb{N}$, it is the case that either $z_{n+1}-z_n=a$ or $z_{n+1}-z_n=a+1$ for some fixed $a\in\mathbb{N}$.
\end{definition}
\noindent It is worth noting here that the quasi-linear sequences we shall encounter do in fact satisfy slightly more stringent conditions than those given in Definition \ref{def2}.  This will be highlighted and explained in Section \ref{sectionscenario3}.  In evaluating the expectations we obtain both exact and asymptotic formulas.

\section{The expectation as a finite sum}
Let the random variable $X_{m,n}$ denote the number of children born such that at least $m$ boys and $n$ girls result.  Observe that over the first $m+n-1$ children, it is not possible to have $m$ boys and $n$ girls, so $X_{m,n} > m+n-1$. Let the random variable $Y$ represent the number of boys born out of the first $m+n-1$ children.  It is clear that
\begin{equation}\label{simpleprob}
\mathbb{P}[Y=k]=\frac{1}{2^{m+n-1}}{{m+n-1} \choose k}.
\end{equation}

We obtain an expression for the expectation of $X_{m,n}$, denoted $\mathbb{E}\left[X_{m,n}\right]$, by conditioning on $Y$.  To this end, consider the random variable $\mathbb{E}\left[X_{m,n}\mid Y=k\right]$. if there are $k$ boys, the remaining $l=(m+n-1)-k$ children are girls. Now, for $k<m$, we have $l \geq n$, and the couple have all the girls they desire. Otherwise, $k \geq m$ and the couple have all the boys they desire.

An inductive argument on the expectation shows that the couple must expect $2t$ children for $t$ to be of a specified gender. In the first case $t=m-k$ for the remaining boys, giving an expectation of $(m+n-1)+2(m-k)$. In the second case $t=n-(m+n-1-k)=k-m+1$ for the remaining girls, giving an expectation of $(m+n-1)+2(k-m+1)$.  This may be summarized as follows:
\begin{equation*}
\mathbb{E}[X_{m,n} \mid Y=k] = m+n-1 +
\begin{cases}
2(m-k),\qquad\, \text{if } k<m; \\
2(k-m+1),\,\,\, \text{if } k\geq m.
\end{cases}
\end{equation*}

The above result, in conjunction with (\ref{simpleprob}) and the formula for conditional expectation \cite{grimmett}, leads to
\begin{align*}
\mathbb{E}\left[X_{m,n}\right]
&=\sum_{k=0}^{m+n-1}\mathbb{E}\left[X_{m,n}\mid Y=k\right]\,\mathbb{P}[Y=k]\\
&=\frac{1}{2^{m+n-1}} \Bigg( \sum_{k=0}^{m-1}(n+3m-2k-1){m+n-1 \choose k} \\
 &\qquad\qquad\qquad\qquad + \sum_{k=m}^{m+n-1}(n-m+2k+1){m+n-1 \choose k}  \Bigg).
\end{align*}
This may be simplified by rearranging and using the well-known results $\sum_{k=0}^r{r \choose k} = 2^r$ and $\sum_{k=0}^r k{r \choose k}=r 2^{r-1}$ to give
\begin{align}\label{finiteexp2}
\mathbb{E}\left[X_{m,n}\right]
&=\frac{1}{2^{m+n-1}} \Bigg( \sum_{k=0}^{m+n-1} (n-m+2k+1){m+n-1 \choose k}\nonumber\\
&\qquad\qquad\qquad\quad + \sum_{k=0}^{m-1}\big((n+3m-2k-1)-(n-m+2k+1) \big){m+n-1 \choose k} \Bigg)\nonumber\\
&=\frac{1}{2^{m+n-1}} \Bigg( 2\sum_{k=0}^{m+n-1}k{m+n-1 \choose k}+(n-m+1)\sum_{k=0}^{m+n-1}{m+n-1 \choose k}  \nonumber\\
&\qquad\qquad\qquad\quad + 2\sum_{k=0}^{m-1}\big(2(m-k)-1\big){m+n-1 \choose k} \Bigg)\nonumber\\
&=\frac{1}{2^{m+n-1}} \Bigg(2\cdot2^{m+n-2}(m+n-1)+2^{m+n-1}(n-m+1) \nonumber\\
&\qquad\qquad\qquad\quad + 2\sum_{k=0}^{m-1}\big(2(m-k)-1\big){m+n-1 \choose k} \Bigg)\nonumber\\
&=2n+\frac{1}{2^{m+n-2}}\sum_{k=0}^{m-1}\big(2(m-k)-1\big){m+n-1 \choose k}.
\end{align}

\section{Scenario 1}
We first consider the behavior of $\mathbb{E}\left[X_{m,n}\right]$ as $n$ increases without limit whilst keeping $m$ fixed.  To this end, let us set
\[f(m,n)=\frac{1}{2^{m+n-2}}\sum_{k=0}^{m-1}\big(2(m-k)-1\big){m+n-1 \choose k},\]
and examine what happens to $f(m,n)$ as $n$ tends to infinity for any fixed $m\in\mathbb{N}$.  First, $1\leq 2(m-k)-1< 2m$ when $0\leq k \leq m-1$.  Next, consider the binomial coefficient ${m+n-1 \choose k}$ for fixed $m$ and some fixed value of $k$ such that $0\leq k \leq m-1$.  This is a polynomial in $n$ of degree $k$, which we denote by $g_{k,m}(n)$.  Note that there exists some $N\in\mathbb{N}$ such that $g_{m-1,m}(n)\geq g_{k,m}(n)$ for each $k$, $0\leq k \leq m-1$, and for all $n>N$.  Therefore, when $n>N$, it is the case that
\begin{align*}
f(m,n)
&< \frac{2m}{2^{m+n-2}}\sum_{k=0}^{m-1}g_{k,m}(n)\\
&\leq \frac{2m^2 g_{m-1,m}(n)}{2^{m+n-2}}\\
&=\frac{m^2}{2^{m-3}}\cdot\frac{g_{m-1,m}(n)}{2^n}.
\end{align*}
Since the numerator and denominator of the fraction on the right exhibit polynomial and exponential growth, respectively, it follows that $f(m,n)\rightarrow 0$ as $n\rightarrow \infty$.

Thus, for any fixed $m\in\mathbb{N}$, $2n$ is an asymptotic formula for $\mathbb{E}\left[X_{m,n}\right]$ in a particularly strong sense.  Not only is it true that
\[\frac{\mathbb{E}\left[X_{m,n}\right]}{2n}\rightarrow 1\quad\text{as}\quad n\rightarrow \infty,\]
 but also $\mathbb{E}\left[X_{m,n}\right]-2n\rightarrow 0$.  With $\langle x\rangle$ denoting the nearest integer to $x$, we are able to deduce from this that $\big(\left\langle\mathbb{E}\left[X_{m,n}\right]\right\rangle\big)_{n\geq 1}$ is an eventually-linear sequence, a result that may in fact be argued heuristically.  As an example, the first 14 terms of $\big(\left\langle\mathbb{E}[X_{5,n}]\right\rangle\big)_{n\geq 1}$ are given by
 \[10, 10, 11, 11, 12, 14, 15, 17, 19, 20, 22, 24, 26, 28,\ldots,\]
 and is linear from the $10$th term onwards.

 Furthermore, by considering the expression $f(m,n)$, it may be shown that, for fixed $m$,
 \[\mathbb{E}\left[X_{m,n}\right]=2n+\frac{h(n)}{2^{n+m-2}(m-1)!},\]
where $h(n)$ is a monic polynomial of degree $m-1$.  By way of an example,
\[\mathbb{E}\left[X_{5,n}\right]=2n+\frac{n^4+22n^3+203n^2+950n+1920}{2^{n+3}4!}.\]

\section{Scenario 2}
Now let $a$ and $b$ be fixed positive integers such that, without loss of generality, $a<b$.  We consider the behavior, as $r$ tends to infinity, of $\mathbb{E}\left[X_{m,n}\right]$ for the situation in which $(m,n)=(ra,rb)$; in other words, we look at what happens in the limit as $m$ and $n$ remain in fixed proportion.  From (\ref{finiteexp2}) we have
\begin{align}\label{tailbin}
\mathbb{E}[X_{ra,rb}]
&=2rb+\frac{1}{2^{r(a+b)-2}}\sum_{k=0}^{ra-1}\big(2(ra-k)-1\big){r(a+b)-1 \choose k}\nonumber\\
&<2rb+\frac{2ra}{2^{r(a+b)-2}}\sum_{k=0}^{ra-1}{r(a+b)-1 \choose k}\nonumber\\
&=2rb+4ra\Bigg(\frac{1}{2^{r(a+b)-1}}\sum_{k=0}^{ra-1}{r(a+b)-1 \choose k}\Bigg).
\end{align}

Hoeffding's inequality \cite{hoeffding,wikihoeffding} gives us information concerning the cumulative size of the tails of probability distributions.  For the case of a binomial distribution $S\sim \text{B}(n,p)$ and $\epsilon>0$ we have the following result \cite{wikihoeffding}:
\begin{equation}\label{hoeff}
\mathbb{P}[S\leq n(p-\epsilon)]\leq \exp\left(-2\epsilon^2 n\right).
\end{equation}
On setting $p=\frac{1}{2}$, $n(p-\epsilon)=ra-1$ and $n=r(a+b)-1$, we obtain
\[\epsilon=\frac{r(b-a)+1}{2\big(r(a+b)-1\big)}\]
(noting that $b>a$, so that $\epsilon$ is indeed positive). Thus, from (\ref{hoeff}),
\begin{align*}
\mathbb{P}[S\leq ra-1]
&\leq \exp\left(-2\left(\frac{r(b-a)+1}{2\big(r(a+b)-1\big)}\right)^2 \big(r(a+b)-1\big)\right)\\
&=\exp\left(-\frac{\big(r(b-a)+1\big)^2}{2\big(r(a+b)-1\big)}\right).
\end{align*}
Since, for fixed $a$ and $b$,
\[ra \exp\left(-\frac{\big(r(b-a)+1\big)^2}{2\big(r(a+b)-1\big)}\right)\rightarrow 0\quad\text{as}\quad r\rightarrow\infty,\]
 it may be seen, from (\ref{tailbin}), that when $m$ and $n$ remain in proportion we have both
\[\frac{\mathbb{E}[X_{ra,rb}]}{2rb}\rightarrow 1\quad\text{and}\quad\mathbb{E}[X_{ra,rb}]-2rb\rightarrow 0\quad\text{as}\quad r\rightarrow \infty,\]
emphasizing here that the assumption $a<b$ is indeed necessary for this result to hold.  Thus $\big(\left\langle\mathbb{E}[X_{ra,rb}]\right\rangle\big)_{n\geq 1}$ is an eventually-linear sequence, exhibiting qualitatively similar behavior to the case in which $m$ was kept fixed.  To give an example, $\big(\left\langle\mathbb{E}[X_{20r,21r}]\right\rangle\big)_{n\geq 1}$ is linear from the 242nd term onwards.

\section{The expectation as an infinite sum}\label{infsection}
We use the standard definition for expectation:
\begin{equation*}
\mathbb{E}[X]=\sum_x x\mathbb{P}[X=x]
\end{equation*}
in order to obtain an expression for $\mathbb{E}[X_{m,n}]$ comprising an infinite series.  Note that $X_{m,n}$ can take any integer value greater than or equal to $m+n$. To calculate the probability $\mathbb{P}[X_{m,n}=k]$ we first count the number of possible strings of length $k$ in an alphabet comprising two symbols that satisfy our requirements.  This number is then multiplied by $\frac{1}{2^k}$, as each outcome occurs with this probability. To this end, consider the last child born. If this was a boy, we require precisely $m-1$ boys in the first $k-1$, and if a girl, we require precisely $n-1$ girls in the first $k-1$. Thus the number we seek is ${{k-1} \choose {m-1}}+{{k-1} \choose {n-1}}$ and the expectation can be expressed as:
\begin{equation*}
\mathbb{E}[X_{m,n}]=\sum_{k=m+n}^\infty\frac{k}{2^k}\Bigg( {{k-1} \choose m-1}+{{k-1} \choose n-1}\Bigg).
\end{equation*}
Applying the identity ${{k-1} \choose m-1}=\frac{m}{k}{k \choose m}$ provides us with the alternative form:
\begin{equation}\label{infformula}
\mathbb{E}[X_{m,n}]=\sum_{k=m+n}^\infty\frac{1}{2^k}\Bigg( m{k \choose m}+n{k \choose n}\Bigg).
\end{equation}

In Section \ref{sectionscenario3} we go on to consider the case for which $n=m+j$ for some fixed $j\in\mathbb{N}$.  The formulation for $\mathbb{E}[X_{m,n}]$ as an infinite sum given above is more convenient for studying the expectation's behavior when $m$ and $n$ are kept a fixed distance apart.  We shall also make use of a result from \cite{griffiths2}:
\begin{equation}\label{myres}
\sum_{k=2r}^\infty\frac{1}{2^{k}}{k \choose r}=r\Bigg(1+\frac{1}{2^{2r}}\binom{2r}{r}\Bigg),
\end{equation}
a consequence of Stirling's formula \cite{griffiths1,knuth}:
\begin{equation}\label{centralstirling}
\binom{2m}{m}\sim\frac{2^{2m}}{\sqrt{m\pi}},
\end{equation}
and a result which follows from Stirling's formula:
\begin{equation}\label{stirzero}
\frac{1}{2^{2m}}\binom{2m}{m}\rightarrow 0\quad\text{as}\quad m\rightarrow \infty.
\end{equation}

\section{Scenario 3}\label{sectionscenario3}
In this final section we set $n=m+j$, where $j$ is a fixed non-negative integer, and consider what happens to the expectation as $m$ increases without limit, noting that a formula for the special case $j=0$ is derived in \cite{griffiths2}, leading to sequence \seqnum{A159061} in the \textit{On-line Encyclopedia of Integer Sequences} \cite{sloane}.  From (\ref{infformula}) we have
\begin{align}\label{finalsum}
\mathbb{E}\left[X_{m,m+j}\right]
&=\sum_{k=2m+j}^\infty\frac{1}{2^k}\Bigg(m{k \choose m}+(m+j){k \choose m+j}\Bigg)\nonumber\\
&=\sum_{k=2m}^\infty\frac{m}{2^k}{k \choose m}-\sum_{k=2m}^{2m+j-1}\frac{m}{2^k}{k \choose m}\nonumber\\
&\qquad\qquad\quad+\sum_{k=2(m+j)}^\infty\frac{m+j}{2^k}{k \choose m+j}+\sum_{k=2m+j}^{2m+2j-1}\frac{m+j}{2^k}{k \choose m+j}.
\end{align}
On considering just the finite sums above, we obtain
\begin{align}\label{finalfinitesum}
-\sum_{k=2m}^{2m+j-1}&\frac{m}{2^k}{k \choose m}+\sum_{k=2m+j}^{2m+2j-1}\frac{m+j}{2^k}{k \choose m+j}\nonumber\\
&\qquad =-\frac{1}{2^{2m}}\sum_{k=0}^{j-1}\frac{m(2m+1)_k}{2^k(m+1)_k}{2m \choose m}+\frac{1}{2^{2m}}\sum_{k=j}^{2j-1}\frac{m(2m+1)_k}{2^k(m+1)_k}{2m \choose m}\nonumber\\
&\qquad\qquad\quad+\frac{j}{2^{2m}}\sum_{k=2m+j}^{2m+2j-1}\frac{(2m+1)_k}{2^k(m+1)_k}{2m \choose m}\nonumber\\
&\qquad =\frac{m}{2^{2m}}\binom{2m}{m}\left(\sum_{k=j}^{2j-1}\frac{(2m+1)_k}{2^k(m+1)_k}-\sum_{k=0}^{j-1}\frac{(2m+1)_k}{2^k(m+1)_k}\right)\nonumber\\
&\qquad\qquad\quad+\frac{j}{2^{2m}}{2m \choose m}\sum_{k=2m+j}^{2m+2j-1}\frac{(2m+1)_k}{2^k(m+1)_k},
\end{align}
where the \textit{Pochhammer symbol} $(t)_n$ is defined by $t(t+1)\cdots(t+n-1)$, which is also known as the \textit{rising factorial}.  Note that $(t)_0=1$ by definition.

Since
\begin{equation}\label{small}
\frac{(2m+1)_k}{2^k(m+1)_k}\leq 1
\end{equation}
for all non-negative integers $k$, it is the case that
\[j\sum_{k=2m+j}^{2m+2j-1}\frac{(2m+1)_k}{2^k(m+1)_k}\leq j^2.\]
Then, for fixed $j$, it follows from (\ref{stirzero}) that
\begin{equation}\label{jgoestozero}
\frac{j}{2^{2m}}{2m \choose m}\sum_{k=2m+j}^{2m+2j-1}\frac{(2m+1)_k}{2^k(m+1)_k}\rightarrow 0\quad\text{as}\quad m\rightarrow \infty.
\end{equation}

Next, for $k$ such that $0\leq k\leq j-1$,
\begin{align}\label{pochres}
\frac{(2m+1)_{j+k}}{2^{j+k}(m+1)_{j+k}}-\frac{(2m+1)_k}{2^k(m+1)_k}
&=\frac{(2m+1)_k}{2^k(m+1)_k}\left(\frac{(2m+k+1)_j}{2^j(m+k+1)_j}-1\right)\nonumber\\
&=\frac{(2m+1)_k}{2^k(m+1)_k}\left(-\frac{G_{j,k}(m)}{H_{j,k}(m)}\right),
\end{align}
where, for fixed $j$ and $k$, $G_{j,k}(m)$ and $H_{j,k}(m)$ are polynomials in $m$ of degrees $j-1$ and $j$, respectively, and, without loss of generality, $H_{j,k}(m)$ is monic. The leading coefficient of $G_{j,k}(m)$ is in fact a function of $j$ and $k$, and, out of all the values of $k$ from $0$ to $j-1$, is largest when $k=j-1$ (as is easily shown to be true).  The leading coefficient of $G_{j,j-1}(m)$ is given by $\frac{j(3j-1)}{4}$.  From this it follows that
\begin{equation}\label{polylimit}
m\frac{G_{j,j-1}(m)}{H_{j,j-1}(m)}\rightarrow\frac{j(3j-1)}{4}\quad\text{as}\quad m\rightarrow\infty.
\end{equation}

Now, using (\ref{small}) and (\ref{pochres}), we have
\begin{align}\label{modulus}
\frac{m}{2^{2m}}\binom{2m}{m}&\left|\sum_{k=j}^{2j-1}\frac{(2m+1)_k}{2^k(m+1)_k}-\sum_{k=0}^{j-1}\frac{(2m+1)_k}{2^k(m+1)_k}\right|\nonumber\\
&=\frac{m}{2^{2m}}\binom{2m}{m}\left|\sum_{k=0}^{j-1}\frac{(2m+1)_k}{2^k(m+1)_k}\left(-\frac{G_{j,k}(m)}{H_{j,k}(m)}\right)\right|\nonumber\\
&\leq \frac{1}{2^{2m}}\binom{2m}{m}\left|\sum_{k=0}^{j-1}m\frac{G_{j,k}(m)}{H_{j,k}(m)}\right|
\end{align}
We know from (\ref{polylimit}) that
\begin{equation}\label{moduluslim}
\left|\sum_{k=0}^{j-1}m\frac{G_{j,k}(m)}{H_{j,k}(m)}\right|\rightarrow c\quad\text{as}\quad m\rightarrow\infty
\end{equation}
for some some $c\in\mathbb{R}$ which depends on $j$.  From (\ref{stirzero}), (\ref{modulus}) and (\ref{moduluslim}), it then follows that
\begin{equation}\label{limzero}
\frac{m}{2^{2m}}\binom{2m}{m}\left(\sum_{k=j}^{2j-1}\frac{(2m+1)_k}{2^k(m+1)_k}-\sum_{k=0}^{j-1}\frac{(2m+1)_k}{2^k(m+1)_k}\right)\rightarrow 0\quad\text{as}\quad m\rightarrow \infty.
\end{equation}
We may now combine results (\ref{myres}), (\ref{centralstirling}), (\ref{finalsum}), (\ref{finalfinitesum}), (\ref{jgoestozero}) and (\ref{limzero}) to give
\begin{align*}
\mathbb{E}\left[X_{m,m+j}\right]
&\sim\sum_{k=2m}^\infty\frac{m}{2^k}{k \choose m}+\sum_{k=2(m+j)}^\infty\frac{m+j}{2^k}{k \choose m+j}\\
&=m\Bigg(1+\frac{1}{2^{2m}}\binom{2m}{m}\Bigg)+(m+j)\Bigg(1+\frac{1}{2^{2(m+j)}}\binom{2(m+j)}{m+j}\Bigg)\\
&\sim m\left(1+\frac{1}{\sqrt{m\pi}}\right)+(m+j)\left(1+\frac{1}{\sqrt{(m+j)\pi}}\right).
\end{align*}
Finally, on tidying up (remembering that $j$ is fixed), we obtain the following asymptotic formula:
\[\mathbb{E}\left[X_{m,m+j}\right]\sim 2m\left(1+\frac{1}{\sqrt{m\pi}}\right).\]

Notice that from this result we may deduce, for fixed $j$, that $\left(\left\langle\mathbb{E}\left[X_{m,m+j}\right]\right\rangle\right)_{n\geq 1}$ is not an eventually-linear sequence.  These sequences do, however, turn out to be quasi-linear.  By way of an example we obtain, using the exact formula (\ref{infformula}) with $j=3$, the following first few terms of $\left(\left\langle\mathbb{E}\left[X_{m,m+3}\right]\right\rangle\right)_{n\geq 1}$:
\[8, 10, 12, 15, 17, 19, 21, 23, 25, 28, 30, 32, 34, 36, 38, 40, 42, 45,\ldots\]
Such sequences are in fact quasi-linear in a particularly strong sense, as we now describe:
\begin{definition}
Let $\left(x_n\right)_{n\geq 1}$ be a sequence of positive integers, and suppose that the sequence  $\left(d_n\right)_{n\geq 1}$ has the following property.  The first $x_1$ terms of $\left(d_n\right)_{n\geq 1}$ comprise a finite linear sequence with common difference $a$ for some $a\in\mathbb{N}$, then $d_{x_1+1}-d_{x_1}=a+1$, and the terms of $\left(d_n\right)_{n\geq 1}$ numbered $x_{1}+1$ to $x_2$ form a finite linear sequence with common difference $a$, and so on.  Then we term $\left(d_n\right)_{n\geq 1}$ \textit{strongly quasi-linear} if $\left(x_n\right)_{n\geq 1}$ is strictly increasing.
\end{definition}
\noindent For example, the sequence $\left(\left\langle\mathbb{E}\left[X_{m,m+3}\right]\right\rangle\right)_{n\geq 1}$ given above is strongly quasi-linear.  We have $x_1=3$, $x_2=6$, $x_3=8$, and so on.

\section{Acknowledgement}
The authors would like to thank an anonymous referee for making suggestions that have helped improved the clarity of this article.

\begin{thebibliography}{9}

\bibitem{griffiths1} M. Griffiths, \textit{The Backbone of Pascal's Triangle}, United Kingdom Mathematics Trust, 2008.

\bibitem{griffiths2} M. Griffiths,  How many children?  \textit{Math. Gaz.} \textbf{90} (2006), 146--149.

\bibitem{grimmett} G. Grimmett and D. Stirzaker,  \textit{Probability and Random Processes}, 3rd edition, Oxford University Press, 2001.

\bibitem{hoeffding} W. Hoeffding,  Probability inequalities for sums of bounded random variables,  \textit{J. Amer. Statist. Assoc.} \textbf{58} (1963), 13--30.

\bibitem{knuth} D. E. Knuth, \textit{The Art of Computer Programming, Vol. 1: Fundamental Algorithms}, third edition, Addison-Wesley, 1997.

\bibitem{sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org/}.

\bibitem{wikihoeffding} Wikipedia contributors, \textit{Hoeffding's inequality},  Wikipedia, The Free Encyclopedia (2012). \url{http://en.wikipedia.org/wiki/Hoeffding's_inequality}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B25; Secondary 05A10, 40A05.

\noindent \emph{Keywords: } 
arithmetic progression, binomial coefficient, discrete random
variable, expected value.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A159061}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 14 2012;
revised version received  January 1 2013.
Published in {\it Journal of Integer Sequences}, January 1 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}