# Solution of a 2D Recurrence sequence

Can we solve the following recurrence relation: $$a_{m,n} = 1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}$$ with $$a_{0,n}=a_{m,0}=0$$? If not, can we get an estimate of the growth of $$a_{m,n}?$$

I encountered this question when analyzing a 2D random walk on $$R_+^2$$ with boundaries at $$x = m$$ and $$y = n$$.

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$$.

• I'm more interested in the asymptotic behavior of $a_{m,n}$ if a closed form solution cannot be obtained. Is there a way to do that? – neverevernever Feb 11 at 17:40
• I have added the asymptotics for large values of the indices. – Iosif Pinelis Feb 12 at 21:31

If $$P_k(t) = \sum_{m=0}^k a_{m,k-n} t^m$$ is the generating function of an ascending antidiagonal, we have

$$P_k(t) = \frac{t^k-t}{t-1} + \frac{1+t}{2} P_{k-1}(t), \ P_0(t) = 0$$ and this can be solved:

$$P_k(t) = \frac{2 t + 2t^{k+1} - 4 t ((t+1)/2)^k}{(t-1)^2}$$

Here are two observations. Both struck me as surprising at first and then not so surprising at all.

• $$a(m,n)$$ is the expected number of flips of a fair coin until one gets either $$m$$ heads or $$n$$ tails.

• Consider the recurrence relation $$b_{m,n}=b(m-1,n)+b(m,n-1)+2^{m+n-2}$$ with $$b_{0,n}=b_{m,0}=0.$$ Then $$a_{m,n}=\frac{b_{m,n}}{2^{m+n-2}}.$$

I suppose the first observation translates to the behavior of right/up walks in a rectangle. The second observation easily results from the recurrence for the $$a_{m,n}.$$

Here is a table of the first few values $$b_{m,n}:$$

$$\left[ \begin {array}{ccccccccc} 1&3&7&15&31&63&127&255&511 \\ 3&10&25&56&119&246&501&1012&2035 \\ 7&25&66&154&337&711&1468&2992&6051 \\ 15&56&154&372&837&1804&3784&7800&15899 \\ 31&119&337&837&1930&4246&9054&18902&38897 \\ 63&246&711&1804&4246&9516&20618&43616&90705 \\ 127&501&1468&3784&9054&20618&45332&97140&204229 \\ 255&1012&2992&7800&18902&43616&97140&210664& 447661\\ 511&2035&6051&15899&38897&90705&204229& 447661&960858\end {array} \right]$$

One observes (and then easily proves) that

• The table reduced $$\bmod 2$$ is a Sierpinski triangle.
• $$b_{1,n}=1\cdot2^n-1.$$
• $$b_{2,n}=2\cdot 2^{n+1}-(n+4).$$
• $$b_{3,n}= 3\cdot 2^{n+2}-\frac{n^2+9n+24}2.$$.
• $$b_{4,n}= 4\cdot 2^{n+3}-\frac{n^3+15n^2+86n+192}6.$$
• $$b_{5,n}=5\cdot 2^{n+4}-\frac{n^4+22n^3+203n^2+950n+1920}{24}.$$

By induction, it is immediate that $$a_{m,n}\le 2\min(m,n)$$. In addition, when $$m$$ is fixed and $$n>m$$ we have $$a_{m,n}=2m-P_m(n)/2^n$$, where $$P_m(x)$$ is a polynomial of degree $$m$$, so $$2m$$ is an exponentially good bound. For $$m=n$$, it seems that $$a_{n,n}=2n(1-1/\sqrt{\pi n}+o(1/\sqrt{n}))$$, but I have not taken the time to prove it.

Added: numerically $$a_{n,n}=2n(1-1/\sqrt{\pi n}+1/(8\sqrt{\pi n^3})-1/(128\sqrt{\pi n^5})+...)$$

Looks like a well-known expansion, probably in Knuth vol 1.

• For m=n, do you have any intuition for the asymptotics? – neverevernever Feb 11 at 14:04
• yes, see my addition – Henri Cohen Feb 11 at 14:28