Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{multline*} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n \\ =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{multline*} whence \begin{align*} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align*} for $s,t$ in $(-1,1)$, so that \begin{equation*} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \tag{0} \end{equation*} for natural $p,q$.

Added: As an illustration of the use of formula (0), let us obtain the asymptotics of $a_{p,q}$ as $p,q\to\infty$. To do that, it is convenient to use the central limit theorem (CLT) of probability theory, applied here to the binomial distribution. Indeed, note that \begin{equation*} \Big(\frac12\Big)^k \binom kj=P(X_k=j), \end{equation*} where $X_k$ has the binomial distribution with parameters $k$ and $1/2$, so that, by the CLT, \begin{equation*} P(X_k\le x)\underset{k\to\infty}\longrightarrow\Phi(g_x(k)) \end{equation*} uniformly in all real $x$, where $\Phi$ is the standard normal cumulative distribution function and \begin{equation*} g_x(k):=\frac{x-k/2}{\sqrt{k/4}}=\frac{2x-k}{\sqrt k}=\frac{2x}{\sqrt k}-\sqrt k, \end{equation*} which is decreasing in $k$ for each $x\ge0$. Without loss of generality, \begin{equation*} p\ge q. \end{equation*} Interchanging the order of summation in (10), we have \begin{align*} a_{p,q}&:=\sum _{k=0}^{p+q-2} \sum _{j=\max (0,1+k-q)}^{\min (p-1,k)} P(X_k=j) \\ &=\sum _{k=0}^{p+q-2}P(\max (0,1+k-q)\le X_k\le\min (p-1,k)) \\ &=S_1+S_2+S_3=p+T_1-T_2, \tag{1} \end{align*} where \begin{align*} S_1&:=\sum _{k=0}^{q-1}P(0\le X_k\le k)=q, \\ S_2&:=\sum _{k=q}^{p-1}P(1+k-q\le X_k\le k) =p-q-\sum _{k=q}^{p-1}P(X_k\le k-q), \\ S_3&:=\sum _{k=p}^{p+q-2}P(1+k-q\le X_k\le p-1) \\ &=\sum _{k=p}^{p+q-2}[P(X_k\le p-1)-P(X_k\le k-q)], \\ T_1&:=\sum _{k=p}^{p+q-2}P(X_k\le p-1) =\sum _{k=p}^{p+q-2}\Phi(g_{p-1}(k))+o(q), \\ T_2&:=\sum _{k=q}^{p+q-2}P(X_k\le k-q)=\sum _{k=q}^{p+q-2}\Phi(g_{k-q}(k))+o(p) \\ &=p-1-U+o(p)=p-U+o(p), \quad U:=\sum _{k=q}^{p+q-2}\Phi(g_{q}(k)); \tag{2} \end{align*} here we used the identities $g_{k-q}(k)=-g_{q}(k)$ and $\Phi(-u)=1-\Phi(u)$.

Let now $A_p$ vary with $p$ so that $A_p\to\infty$, $A_p=o(\sqrt p)$, and \begin{equation*} k_p:=2p-A_p\sqrt{2p}\in\mathbb Z. \end{equation*} Then for integers $k$ in $[p,k_p]$ we have \begin{equation*} g_{p-1}(k)=g_p(k)+o(1),\quad g_p(k)= \frac{2p-k}{\sqrt k}\ge\frac{2p-k_p}{\sqrt k_p}\ge A_p\to\infty, \end{equation*} so that $\Phi(g_{p-1}(k))\to1$ uniformly in integers $k$ in $[p,k_p]$ and hence \begin{multline*} T_{11}:=\sum _{k=p}^{\min(p+q-2,k_p)}P(X_k\le p-1) =\sum _{k=p}^{\min(p+q-2,k_p)}\Phi(g_{p-1}(k))+o(q) \\ =\min(p+q-2,k_p)-(p-1)+o(q)+o(q)=q+o(p), \end{multline*} because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. Also, \begin{equation*} 0\le T_1-T_{11}=\sum _{k=1+\min(p+q-2,k_p)}^{p+q-2}P(X_k\le p-1) \le(p+q-2)-\min(p+q-2,k_p)=o(p), \end{equation*} again because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. So, \begin{equation*} T_1=q+o(p). \tag{3} \end{equation*}

The term $U$ is estimated similarly to $T_1$. Write \begin{equation*} U=U_1+U_2+U_3, \end{equation*} where \begin{align*} U_1&:=\sum _{k=q}^{k_q}\Phi(g_{q}(k)), \\ U_2&:=\sum_{k=1+k_q}^{\min(l_q,p+q-2)}\Phi(g_{q}(k)), \\ U_3&:=\sum_{k=1+\min(l_q,p+q-2)}^{p+q-2}\Phi(g_{q}(k)), \end{align*} where \begin{equation*} l_q:=2q+A_q\sqrt{p+q}. \end{equation*} The term $U_1$ is estimated similarly to, and a bit more simply than, $T_{11}$, and we get \begin{equation*} U_1=q+o(q). \end{equation*} The term $U_2$ is estimated similarly to $T_1-T_{11}$, and we get \begin{equation*} U_2=o(q). \end{equation*} For integers $k$ in $[l_q,p+q]$ we have \begin{equation*} g_q(k)=\frac{2q-k}{\sqrt k}\le\frac{2q-l_q}{\sqrt k}=\frac{-A_q\sqrt{p+q}}{\sqrt k} \le-A_q\to-\infty, \end{equation*} so that $\Phi(g_q(k))\to0$ uniformly in integers $k$ in $[l_q,p+q]$ and hence \begin{equation*} U_3=o((p+q-2)-\min(l_q,p+q-2))=o(p). \end{equation*} So, \begin{equation*} U=q+o(p). \tag{4} \end{equation*} Collecting the pieces (1)--(4) together, we get \begin{equation*} a_{p,q}=p+T_1-T_2=p+T_1-p+U+o(p)=p+q-p+q+o(p)=2q+o(p), \end{equation*} under the assumption $p\ge q$. Without this assumption, \begin{equation*} a_{p,q}=2\min(p,q)+o(\max(p,q)) \end{equation*} as $p,q\to\infty$.

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{multline*} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n \\ =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{multline*} whence \begin{align*} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align*} for $s,t$ in $(-1,1)$, so that \begin{equation*} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \tag{0} \end{equation*} for natural $p,q$.

Added: As an illustration of the use of formula (0), let us obtain the asymptotics of $a_{p,q}$ as $p,q\to\infty$. To do that, it is convenient to use the central limit theorem (CLT) of probability theory, applied here to the binomial distribution. Indeed, note that \begin{equation*} \Big(\frac12\Big)^k \binom kj=P(X_k=j), \end{equation*} where $X_k$ has the binomial distribution with parameters $k$ and $1/2$, so that, by the CLT, \begin{equation*} P(X_k\le x)\underset{k\to\infty}\longrightarrow\Phi(g_x(k)) \end{equation*} uniformly in all real $x$, where $\Phi$ is the standard normal cumulative distribution function and \begin{equation*} g_x(k):=\frac{x-k/2}{\sqrt{k/4}}=\frac{2x-k}{\sqrt k}=\frac{2x}{\sqrt k}-\sqrt k, \end{equation*} which is decreasing in $k$ for each $x\ge0$. Without loss of generality, \begin{equation*} p\ge q. \end{equation*} Interchanging the order of summation in (1), we have \begin{align*} a_{p,q}&:=\sum _{k=0}^{p+q-2} \sum _{j=\max (0,1+k-q)}^{\min (p-1,k)} P(X_k=j) \\ &=\sum _{k=0}^{p+q-2}P(\max (0,1+k-q)\le X_k\le\min (p-1,k)) \\ &=S_1+S_2+S_3=p+T_1-T_2, \tag{1} \end{align*} where \begin{align*} S_1&:=\sum _{k=0}^{q-1}P(0\le X_k\le k)=q, \\ S_2&:=\sum _{k=q}^{p-1}P(1+k-q\le X_k\le k) =p-q-\sum _{k=q}^{p-1}P(X_k\le k-q), \\ S_3&:=\sum _{k=p}^{p+q-2}P(1+k-q\le X_k\le p-1) \\ &=\sum _{k=p}^{p+q-2}[P(X_k\le p-1)-P(X_k\le k-q)], \\ T_1&:=\sum _{k=p}^{p+q-2}P(X_k\le p-1) =\sum _{k=p}^{p+q-2}\Phi(g_{p-1}(k))+o(q), \\ T_2&:=\sum _{k=q}^{p+q-2}P(X_k\le k-q)=\sum _{k=q}^{p+q-2}\Phi(g_{k-q}(k))+o(p) \\ &=p-1-U+o(p)=p-U+o(p), \quad U:=\sum _{k=q}^{p+q-2}\Phi(g_{q}(k)); \tag{2} \end{align*} here we used the identities $g_{k-q}(k)=-g_{q}(k)$ and $\Phi(-u)=1-\Phi(u)$.

Let now $A_p$ vary with $p$ so that $A_p\to\infty$, $A_p=o(\sqrt p)$, and \begin{equation*} k_p:=2p-A_p\sqrt{2p}\in\mathbb Z. \end{equation*} Then for integers $k$ in $[p,k_p]$ we have \begin{equation*} g_{p-1}(k)=g_p(k)+o(1),\quad g_p(k)= \frac{2p-k}{\sqrt k}\ge\frac{2p-k_p}{\sqrt k_p}\ge A_p\to\infty, \end{equation*} so that $\Phi(g_{p-1}(k))\to1$ uniformly in integers $k$ in $[p,k_p]$ and hence \begin{multline*} T_{11}:=\sum _{k=p}^{\min(p+q-2,k_p)}P(X_k\le p-1) =\sum _{k=p}^{\min(p+q-2,k_p)}\Phi(g_{p-1}(k))+o(q) \\ =\min(p+q-2,k_p)-(p-1)+o(q)+o(q)=q+o(p), \end{multline*} because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. Also, \begin{equation*} 0\le T_1-T_{11}=\sum _{k=1+\min(p+q-2,k_p)}^{p+q-2}P(X_k\le p-1) \le(p+q-2)-\min(p+q-2,k_p)=o(p), \end{equation*} again because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. So, \begin{equation*} T_1=q+o(p). \tag{3} \end{equation*}

The term $U$ is estimated similarly to $T_1$. Write \begin{equation*} U=U_1+U_2+U_3, \end{equation*} where \begin{align*} U_1&:=\sum _{k=q}^{k_q}\Phi(g_{q}(k)), \\ U_2&:=\sum_{k=1+k_q}^{\min(l_q,p+q-2)}\Phi(g_{q}(k)), \\ U_3&:=\sum_{k=1+\min(l_q,p+q-2)}^{p+q-2}\Phi(g_{q}(k)), \end{align*} where \begin{equation*} l_q:=2q+A_q\sqrt{p+q}. \end{equation*} The term $U_1$ is estimated similarly to, and a bit more simply than, $T_{11}$, and we get \begin{equation*} U_1=q+o(q). \end{equation*} The term $U_2$ is estimated similarly to $T_1-T_{11}$, and we get \begin{equation*} U_2=o(q). \end{equation*} For integers $k$ in $[l_q,p+q]$ we have \begin{equation*} g_q(k)=\frac{2q-k}{\sqrt k}\le\frac{2q-l_q}{\sqrt k}=\frac{-A_q\sqrt{p+q}}{\sqrt k} \le-A_q\to-\infty, \end{equation*} so that $\Phi(g_q(k))\to0$ uniformly in integers $k$ in $[l_q,p+q]$ and hence \begin{equation*} U_3=o((p+q-2)-\min(l_q,p+q-2))=o(p). \end{equation*} So, \begin{equation*} U=q+o(p). \tag{4} \end{equation*} Collecting the pieces (1)--(4) together, we get \begin{equation*} a_{p,q}=p+T_1-T_2=p+T_1-p+U+o(p)=p+q-p+q+o(p)=2q+o(p), \end{equation*} under the assumption $p\ge q$. Without this assumption, \begin{equation*} a_{p,q}=2\min(p,q)+o(\max(p,q)) \end{equation*} as $p,q\to\infty$.

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{multline*} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n \\ =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{multline*} whence \begin{align*} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align*} for $s,t$ in $(-1,1)$, so that \begin{equation*} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \tag{0} \end{equation*} for natural $p,q$.

Added: As an illustration of the use of formula (0), let us obtain the asymptotics of $a_{p,q}$ as $p,q\to\infty$. To do that, it is convenient to use the central limit theorem (CLT) of probability theory, applied here to the binomial distribution. Indeed, note that \begin{equation*} \Big(\frac12\Big)^k \binom kj=P(X_k=j), \end{equation*} where $X_k$ has the binomial distribution with parameters $k$ and $1/2$, so that, by the CLT, \begin{equation*} P(X_k\le x)\underset{k\to\infty}\longrightarrow\Phi(g_x(k)) \end{equation*} uniformly in all real $x$, where $\Phi$ is the standard normal cumulative distribution function and \begin{equation*} g_x(k):=\frac{x-k/2}{\sqrt{k/4}}=\frac{2x-k}{\sqrt k}=\frac{2x}{\sqrt k}-\sqrt k, \end{equation*} which is decreasing in $k$ for each $x\ge0$. Without loss of generality, \begin{equation*} p\ge q. \end{equation*} Interchanging the order of summation in (0), we have \begin{align*} a_{p,q}&:=\sum _{k=0}^{p+q-2} \sum _{j=\max (0,1+k-q)}^{\min (p-1,k)} P(X_k=j) \\ &=\sum _{k=0}^{p+q-2}P(\max (0,1+k-q)\le X_k\le\min (p-1,k)) \\ &=S_1+S_2+S_3=p+T_1-T_2, \tag{1} \end{align*} where \begin{align*} S_1&:=\sum _{k=0}^{q-1}P(0\le X_k\le k)=q, \\ S_2&:=\sum _{k=q}^{p-1}P(1+k-q\le X_k\le k) =p-q-\sum _{k=q}^{p-1}P(X_k\le k-q), \\ S_3&:=\sum _{k=p}^{p+q-2}P(1+k-q\le X_k\le p-1) \\ &=\sum _{k=p}^{p+q-2}[P(X_k\le p-1)-P(X_k\le k-q)], \\ T_1&:=\sum _{k=p}^{p+q-2}P(X_k\le p-1) =\sum _{k=p}^{p+q-2}\Phi(g_{p-1}(k))+o(q), \\ T_2&:=\sum _{k=q}^{p+q-2}P(X_k\le k-q)=\sum _{k=q}^{p+q-2}\Phi(g_{k-q}(k))+o(p) \\ &=p-1-U+o(p)=p-U+o(p), \quad U:=\sum _{k=q}^{p+q-2}\Phi(g_{q}(k)); \tag{2} \end{align*} here we used the identities $g_{k-q}(k)=-g_{q}(k)$ and $\Phi(-u)=1-\Phi(u)$.

Let now $A_p$ vary with $p$ so that $A_p\to\infty$, $A_p=o(\sqrt p)$, and \begin{equation*} k_p:=2p-A_p\sqrt{2p}\in\mathbb Z. \end{equation*} Then for integers $k$ in $[p,k_p]$ we have \begin{equation*} g_{p-1}(k)=g_p(k)+o(1),\quad g_p(k)= \frac{2p-k}{\sqrt k}\ge\frac{2p-k_p}{\sqrt k_p}\ge A_p\to\infty, \end{equation*} so that $\Phi(g_{p-1}(k))\to1$ uniformly in integers $k$ in $[p,k_p]$ and hence \begin{multline*} T_{11}:=\sum _{k=p}^{\min(p+q-2,k_p)}P(X_k\le p-1) =\sum _{k=p}^{\min(p+q-2,k_p)}\Phi(g_{p-1}(k))+o(q) \\ =\min(p+q-2,k_p)-(p-1)+o(q)+o(q)=q+o(p), \end{multline*} because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. Also, \begin{equation*} 0\le T_1-T_{11}=\sum _{k=1+\min(p+q-2,k_p)}^{p+q-2}P(X_k\le p-1) \le(p+q-2)-\min(p+q-2,k_p)=o(p), \end{equation*} again because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. So, \begin{equation*} T_1=q+o(p). \tag{3} \end{equation*}

The term $U$ is estimated similarly to $T_1$. Write \begin{equation*} U=U_1+U_2+U_3, \end{equation*} where \begin{align*} U_1&:=\sum _{k=q}^{k_q}\Phi(g_{q}(k)), \\ U_2&:=\sum_{k=1+k_q}^{\min(l_q,p+q-2)}\Phi(g_{q}(k)), \\ U_3&:=\sum_{k=1+\min(l_q,p+q-2)}^{p+q-2}\Phi(g_{q}(k)), \end{align*} where \begin{equation*} l_q:=2q+A_q\sqrt{p+q}. \end{equation*} The term $U_1$ is estimated similarly to, and a bit more simply than, $T_{11}$, and we get \begin{equation*} U_1=q+o(q). \end{equation*} The term $U_2$ is estimated similarly to $T_1-T_{11}$, and we get \begin{equation*} U_2=o(q). \end{equation*} For integers $k$ in $[l_q,p+q]$ we have \begin{equation*} g_q(k)=\frac{2q-k}{\sqrt k}\le\frac{2q-l_q}{\sqrt k}=\frac{-A_q\sqrt{p+q}}{\sqrt k} \le-A_q\to-\infty, \end{equation*} so that $\Phi(g_q(k))\to0$ uniformly in integers $k$ in $[l_q,p+q]$ and hence \begin{equation*} U_3=o((p+q-2)-\min(l_q,p+q-2))=o(p). \end{equation*} So, \begin{equation*} U=q+o(p). \tag{4} \end{equation*} Collecting the pieces (1)--(4) together, we get \begin{equation*} a_{p,q}=p+T_1-T_2=p+T_1-p+U+o(p)=p+q-p+q+o(p)=2q+o(p), \end{equation*} under the assumption $p\ge q$. Without this assumption, \begin{equation*} a_{p,q}=2\min(p,q)+o(\max(p,q)) \end{equation*} as $p,q\to\infty$.

added 4071 characters in body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{equation} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{equation}\begin{multline*} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n \\ =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{multline*} whence \begin{align} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align}\begin{align*} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align*} for $s,t$ in $(-1,1)$, so that \begin{equation} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{equation}\begin{equation*} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \tag{0} \end{equation*} for natural $p,q$.

Added: As an illustration of the use of formula (0), let us obtain the asymptotics of $a_{p,q}$ as $p,q\to\infty$. To do that, it is convenient to use the central limit theorem (CLT) of probability theory, applied here to the binomial distribution. Indeed, note that \begin{equation*} \Big(\frac12\Big)^k \binom kj=P(X_k=j), \end{equation*} where $X_k$ has the binomial distribution with parameters $k$ and $1/2$, so that, by the CLT, \begin{equation*} P(X_k\le x)\underset{k\to\infty}\longrightarrow\Phi(g_x(k)) \end{equation*} uniformly in all real $x$, where $\Phi$ is the standard normal cumulative distribution function and \begin{equation*} g_x(k):=\frac{x-k/2}{\sqrt{k/4}}=\frac{2x-k}{\sqrt k}=\frac{2x}{\sqrt k}-\sqrt k, \end{equation*} which is decreasing in $k$ for each $x\ge0$. Without loss of generality, \begin{equation*} p\ge q. \end{equation*} Interchanging the order of summation in (1), we have \begin{align*} a_{p,q}&:=\sum _{k=0}^{p+q-2} \sum _{j=\max (0,1+k-q)}^{\min (p-1,k)} P(X_k=j) \\ &=\sum _{k=0}^{p+q-2}P(\max (0,1+k-q)\le X_k\le\min (p-1,k)) \\ &=S_1+S_2+S_3=p+T_1-T_2, \tag{1} \end{align*} where \begin{align*} S_1&:=\sum _{k=0}^{q-1}P(0\le X_k\le k)=q, \\ S_2&:=\sum _{k=q}^{p-1}P(1+k-q\le X_k\le k) =p-q-\sum _{k=q}^{p-1}P(X_k\le k-q), \\ S_3&:=\sum _{k=p}^{p+q-2}P(1+k-q\le X_k\le p-1) \\ &=\sum _{k=p}^{p+q-2}[P(X_k\le p-1)-P(X_k\le k-q)], \\ T_1&:=\sum _{k=p}^{p+q-2}P(X_k\le p-1) =\sum _{k=p}^{p+q-2}\Phi(g_{p-1}(k))+o(q), \\ T_2&:=\sum _{k=q}^{p+q-2}P(X_k\le k-q)=\sum _{k=q}^{p+q-2}\Phi(g_{k-q}(k))+o(p) \\ &=p-1-U+o(p)=p-U+o(p), \quad U:=\sum _{k=q}^{p+q-2}\Phi(g_{q}(k)); \tag{2} \end{align*} here we used the identities $g_{k-q}(k)=-g_{q}(k)$ and $\Phi(-u)=1-\Phi(u)$.

Let now $A_p$ vary with $p$ so that $A_p\to\infty$, $A_p=o(\sqrt p)$, and \begin{equation*} k_p:=2p-A_p\sqrt{2p}\in\mathbb Z. \end{equation*} Then for integers $k$ in $[p,k_p]$ we have \begin{equation*} g_{p-1}(k)=g_p(k)+o(1),\quad g_p(k)= \frac{2p-k}{\sqrt k}\ge\frac{2p-k_p}{\sqrt k_p}\ge A_p\to\infty, \end{equation*} so that $\Phi(g_{p-1}(k))\to1$ uniformly in integers $k$ in $[p,k_p]$ and hence \begin{multline*} T_{11}:=\sum _{k=p}^{\min(p+q-2,k_p)}P(X_k\le p-1) =\sum _{k=p}^{\min(p+q-2,k_p)}\Phi(g_{p-1}(k))+o(q) \\ =\min(p+q-2,k_p)-(p-1)+o(q)+o(q)=q+o(p), \end{multline*} because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. Also, \begin{equation*} 0\le T_1-T_{11}=\sum _{k=1+\min(p+q-2,k_p)}^{p+q-2}P(X_k\le p-1) \le(p+q-2)-\min(p+q-2,k_p)=o(p), \end{equation*} again because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. So, \begin{equation*} T_1=q+o(p). \tag{3} \end{equation*}

The term $U$ is estimated similarly to $T_1$. Write \begin{equation*} U=U_1+U_2+U_3, \end{equation*} where \begin{align*} U_1&:=\sum _{k=q}^{k_q}\Phi(g_{q}(k)), \\ U_2&:=\sum_{k=1+k_q}^{\min(l_q,p+q-2)}\Phi(g_{q}(k)), \\ U_3&:=\sum_{k=1+\min(l_q,p+q-2)}^{p+q-2}\Phi(g_{q}(k)), \end{align*} where \begin{equation*} l_q:=2q+A_q\sqrt{p+q}. \end{equation*} The term $U_1$ is estimated similarly to, and a bit more simply than, $T_{11}$, and we get \begin{equation*} U_1=q+o(q). \end{equation*} The term $U_2$ is estimated similarly to $T_1-T_{11}$, and we get \begin{equation*} U_2=o(q). \end{equation*} For integers $k$ in $[l_q,p+q]$ we have \begin{equation*} g_q(k)=\frac{2q-k}{\sqrt k}\le\frac{2q-l_q}{\sqrt k}=\frac{-A_q\sqrt{p+q}}{\sqrt k} \le-A_q\to-\infty, \end{equation*} so that $\Phi(g_q(k))\to0$ uniformly in integers $k$ in $[l_q,p+q]$ and hence \begin{equation*} U_3=o((p+q-2)-\min(l_q,p+q-2))=o(p). \end{equation*} So, \begin{equation*} U=q+o(p). \tag{4} \end{equation*} Collecting the pieces (1)--(4) together, we get \begin{equation*} a_{p,q}=p+T_1-T_2=p+T_1-p+U+o(p)=p+q-p+q+o(p)=2q+o(p), \end{equation*} under the assumption $p\ge q$. Without this assumption, \begin{equation*} a_{p,q}=2\min(p,q)+o(\max(p,q)) \end{equation*} as $p,q\to\infty$.

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{equation} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{equation} whence \begin{align} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align} for $s,t$ in $(-1,1)$, so that \begin{equation} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{equation} for natural $p,q$.

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{multline*} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n \\ =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{multline*} whence \begin{align*} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align*} for $s,t$ in $(-1,1)$, so that \begin{equation*} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \tag{0} \end{equation*} for natural $p,q$.

Added: As an illustration of the use of formula (0), let us obtain the asymptotics of $a_{p,q}$ as $p,q\to\infty$. To do that, it is convenient to use the central limit theorem (CLT) of probability theory, applied here to the binomial distribution. Indeed, note that \begin{equation*} \Big(\frac12\Big)^k \binom kj=P(X_k=j), \end{equation*} where $X_k$ has the binomial distribution with parameters $k$ and $1/2$, so that, by the CLT, \begin{equation*} P(X_k\le x)\underset{k\to\infty}\longrightarrow\Phi(g_x(k)) \end{equation*} uniformly in all real $x$, where $\Phi$ is the standard normal cumulative distribution function and \begin{equation*} g_x(k):=\frac{x-k/2}{\sqrt{k/4}}=\frac{2x-k}{\sqrt k}=\frac{2x}{\sqrt k}-\sqrt k, \end{equation*} which is decreasing in $k$ for each $x\ge0$. Without loss of generality, \begin{equation*} p\ge q. \end{equation*} Interchanging the order of summation in (1), we have \begin{align*} a_{p,q}&:=\sum _{k=0}^{p+q-2} \sum _{j=\max (0,1+k-q)}^{\min (p-1,k)} P(X_k=j) \\ &=\sum _{k=0}^{p+q-2}P(\max (0,1+k-q)\le X_k\le\min (p-1,k)) \\ &=S_1+S_2+S_3=p+T_1-T_2, \tag{1} \end{align*} where \begin{align*} S_1&:=\sum _{k=0}^{q-1}P(0\le X_k\le k)=q, \\ S_2&:=\sum _{k=q}^{p-1}P(1+k-q\le X_k\le k) =p-q-\sum _{k=q}^{p-1}P(X_k\le k-q), \\ S_3&:=\sum _{k=p}^{p+q-2}P(1+k-q\le X_k\le p-1) \\ &=\sum _{k=p}^{p+q-2}[P(X_k\le p-1)-P(X_k\le k-q)], \\ T_1&:=\sum _{k=p}^{p+q-2}P(X_k\le p-1) =\sum _{k=p}^{p+q-2}\Phi(g_{p-1}(k))+o(q), \\ T_2&:=\sum _{k=q}^{p+q-2}P(X_k\le k-q)=\sum _{k=q}^{p+q-2}\Phi(g_{k-q}(k))+o(p) \\ &=p-1-U+o(p)=p-U+o(p), \quad U:=\sum _{k=q}^{p+q-2}\Phi(g_{q}(k)); \tag{2} \end{align*} here we used the identities $g_{k-q}(k)=-g_{q}(k)$ and $\Phi(-u)=1-\Phi(u)$.

Let now $A_p$ vary with $p$ so that $A_p\to\infty$, $A_p=o(\sqrt p)$, and \begin{equation*} k_p:=2p-A_p\sqrt{2p}\in\mathbb Z. \end{equation*} Then for integers $k$ in $[p,k_p]$ we have \begin{equation*} g_{p-1}(k)=g_p(k)+o(1),\quad g_p(k)= \frac{2p-k}{\sqrt k}\ge\frac{2p-k_p}{\sqrt k_p}\ge A_p\to\infty, \end{equation*} so that $\Phi(g_{p-1}(k))\to1$ uniformly in integers $k$ in $[p,k_p]$ and hence \begin{multline*} T_{11}:=\sum _{k=p}^{\min(p+q-2,k_p)}P(X_k\le p-1) =\sum _{k=p}^{\min(p+q-2,k_p)}\Phi(g_{p-1}(k))+o(q) \\ =\min(p+q-2,k_p)-(p-1)+o(q)+o(q)=q+o(p), \end{multline*} because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. Also, \begin{equation*} 0\le T_1-T_{11}=\sum _{k=1+\min(p+q-2,k_p)}^{p+q-2}P(X_k\le p-1) \le(p+q-2)-\min(p+q-2,k_p)=o(p), \end{equation*} again because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. So, \begin{equation*} T_1=q+o(p). \tag{3} \end{equation*}

The term $U$ is estimated similarly to $T_1$. Write \begin{equation*} U=U_1+U_2+U_3, \end{equation*} where \begin{align*} U_1&:=\sum _{k=q}^{k_q}\Phi(g_{q}(k)), \\ U_2&:=\sum_{k=1+k_q}^{\min(l_q,p+q-2)}\Phi(g_{q}(k)), \\ U_3&:=\sum_{k=1+\min(l_q,p+q-2)}^{p+q-2}\Phi(g_{q}(k)), \end{align*} where \begin{equation*} l_q:=2q+A_q\sqrt{p+q}. \end{equation*} The term $U_1$ is estimated similarly to, and a bit more simply than, $T_{11}$, and we get \begin{equation*} U_1=q+o(q). \end{equation*} The term $U_2$ is estimated similarly to $T_1-T_{11}$, and we get \begin{equation*} U_2=o(q). \end{equation*} For integers $k$ in $[l_q,p+q]$ we have \begin{equation*} g_q(k)=\frac{2q-k}{\sqrt k}\le\frac{2q-l_q}{\sqrt k}=\frac{-A_q\sqrt{p+q}}{\sqrt k} \le-A_q\to-\infty, \end{equation*} so that $\Phi(g_q(k))\to0$ uniformly in integers $k$ in $[l_q,p+q]$ and hence \begin{equation*} U_3=o((p+q-2)-\min(l_q,p+q-2))=o(p). \end{equation*} So, \begin{equation*} U=q+o(p). \tag{4} \end{equation*} Collecting the pieces (1)--(4) together, we get \begin{equation*} a_{p,q}=p+T_1-T_2=p+T_1-p+U+o(p)=p+q-p+q+o(p)=2q+o(p), \end{equation*} under the assumption $p\ge q$. Without this assumption, \begin{equation*} a_{p,q}=2\min(p,q)+o(\max(p,q)) \end{equation*} as $p,q\to\infty$.

added 381 characters in body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{equation} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{equation} whence \begin{equation} P(s,t)=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \end{equation}\begin{align} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align} for $s,t$ in $(-1,1)$, so that \begin{equation} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{equation} for natural $p,q$.

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{equation} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{equation} whence \begin{equation} P(s,t)=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \end{equation} for $s,t$ in $(-1,1)$.

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{equation} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{equation} whence \begin{align} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align} for $s,t$ in $(-1,1)$, so that \begin{equation} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{equation} for natural $p,q$.

Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229