Q:

Find sum with binomial coefficients and powers of 2

Find this sum for positive $n$ and $m$:
$$S(n, m) = \sum_{i=0}^n \frac{1}{2^{m+i+1}}\binom{m+i}{i} + \sum_{i=0}^m \frac{1}{2^{n+i+1}}\binom{n+i}{i}.$$
Obviosly, $S(n,m)=S(m,n)$. Therefore I've tried find
$$T(n,m) = \sum_{i=0}^n \frac{1}{2^{m+i}}\binom{m+i}{i}$$
by $T(n, m+1)$, but in binomial we have $\binom{m+i+1}{i} = \binom{m+i}{i} + \binom{m+i}{i-1}$, and this "$i-1$" brings nothing good. Other combinations like $T(n+1,m+1)+T(n,m)$ also doesn't provide advance.
Any ideas?

A:

Suppose we seek to evaluate
$$S(n,m) = \sum_{q=0}^n \frac{1}{2^{m+q+1}} {m+q\choose q}
+ \sum_{q=0}^m \frac{1}{2^{n+q+1}} {n+q\choose q}$$
using $$T(n,m) = \sum_{q=0}^n \frac{1}{2^{m+q+1}} {m+q\choose q}.$$
Introduce
$${m+q\choose q}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+q}}{z^{q+1}} \; dz.$$
This yields for $T(n,m)$
$$\frac{1}{2^{m+1}}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} 
\sum_{q=0}^n \frac{1}{2^q} \frac{(1+z)^q}{z^q}\; dz
\\ = \frac{1}{2^{m+1}}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} 
\frac{1-(1+z)^{n+1}/2^{n+1}/z^{n+1}}{1-(1+z)/2/z} \; dz
\\ = \frac{1}{2^{m}}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^m
\frac{1-(1+z)^{n+1}/2^{n+1}/z^{n+1}}{2z-(1+z)} \; dz
\\ = \frac{1}{2^{m}}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^m
\frac{1-(1+z)^{n+1}/2^{n+1}/z^{n+1}}{z-1} \; dz.$$
We eliminate the term that does not contribute to get
$$-\frac{1}{2^{m}}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^m
\frac{(1+z)^{n+1}/2^{n+1}/z^{n+1}}{z-1} \; dz
\\ = \frac{1}{2^{m+n+1}}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+m+1}}{z^{n+1}}
\frac{1}{1-z} \; dz.$$
Extracting the residue we obtain
$$\frac{1}{2^{m+n+1}}\sum_{q=0}^n {n+m+1\choose q}.$$
We get for $T(m,n)$
$$\frac{1}{2^{m+n+1}}\sum_{q=0}^m {n+m+1\choose q}$$
which is
$$1-\frac{1}{2^{m+n+1}}\sum_{q=m+1}^{n+m+1} {n+m+1\choose q}
\\= 1-\frac{1}{2^{m+n+1}}\sum_{q=0}^{n} {n+m+1\choose q+m+1}.$$
Collecting the two contributions we obtain
$$1-\frac{1}{2^{m+n+1}}\sum_{q=0}^{n} {n+m+1\choose q+m+1}
+ \frac{1}{2^{m+n+1}}\sum_{q=0}^n {n+m+1\choose q}
= 1,$$
by symmetry  of binomial coefficients  (first term adds the  top $n+1$
coefficients and second term the bottom $n+1$ coefficients).

A:

We first find a recursive formula for $S(n, m)$
\begin{align}
S(n, m) =&\color{red}{ \sum_{i=0}^n \frac{1}{2^{m+i+1}}\binom{m+i}{i}} + \color{blue}{\sum_{i=0}^m \frac{1}{2^{n+i+1}}\binom{n+i}{i}} \\
=&\color{red}{ \sum_{i=0}^n \frac{1}{2^{m+i+1}}\{\binom{m+i - 1}{i} + \binom{m + i - 1}{i-1}\}} + \color{blue}{\sum_{i=0}^m \frac{1}{2^{n+i+1}}\{\binom{n+i-1}{i} + \binom{n+i-1}{i-1}\}} \\
= &\color{red}{ \sum_{i=0}^n \frac{1}{2^{m+i+1}}\binom{m+i - 1}{i} + \sum_{i=0}^n \frac{1}{2^{m+i+1}}\binom{m + i - 1}{i-1}} + \\ 
&\color{blue}{\sum_{i=0}^m \frac{1}{2^{n+i+1}}\binom{n+i-1}{i} + \sum_{i=0}^m \frac{1}{2^{n+i+1}}\binom{n+i-1}{i-1}} \\
= &\color{red}{\frac{1}{2} \sum_{i=0}^n \frac{1}{2^{m+i}}\binom{m+i - 1}{i} + \frac{1}{2} \sum_{i=0}^{n-1} \frac{1}{2^{m+i+1}}\binom{m + i}{i}} + \\ 
&\color{blue}{\frac{1}{2}\sum_{i=0}^m \frac{1}{2^{n+i}}\binom{n+i-1}{i} + \frac{1}{2}\sum_{i=0}^{m-1} \frac{1}{2^{n+i+1}}\binom{n+i}{i}} \\
= &\left(\color{red}{\frac{1}{2} \sum_{i=0}^n \frac{1}{2^{m+i}}\binom{m+i - 1}{i}} + \color{blue}{\frac{1}{2}\sum_{i=0}^{m-1} \frac{1}{2^{n+i+1}}\binom{n+i}{i}}\right) + \\
&\left(\color{red}{\frac{1}{2} \sum_{i=0}^{n-1} \frac{1}{2^{m+i+1}}\binom{m + i}{i}} + \color{blue}{\frac{1}{2}\sum_{i=0}^m \frac{1}{2^{n+i}}\binom{n+i-1}{i}}\right) \\
=& \frac{1}{2}S(n, m - 1) + \frac{1}{2}S(n - 1, m)
\end{align}

We know now that the value of $S(n,m)$ relies only on $S(n-1,m)$ and $S(n, m-1)$.

Given the recursive relationship, another thing we have to do is to compute the values of $S(n,m)$ for base cases. We can easily prove that
$$
S(a, 0) = S(0, a) = 1, \forall a \geq 0
$$
Now, everything is easy now. Please see the table below. The vertical axis is $m$ and the horizontal axis is $n$. All entries $S(a,0)$ and $S(0,a)$ are 1, as shown in the table. As an example, $S(1,1) = \frac{1}{2} S(1,0) + \frac{1}{2}S(0,1) = 1$ (the red entries). For other empty entries, we can do the same and you should convince yourself those entries should also be $1$.

\begin{array}{c|ccccc}
 & 0 & 1 & 2 & 3 & \cdots \\
\hline
0 & 1 & \color{red}{1} & 1 & 1 & \cdots\\
1 & \color{red}{1} & \color{red}{1} &\\
2 & 1 &\\
3 & 1 &\\
\cdots & \cdots &
\end{array}

In summary, we have
$$
S(n, m) = 1
$$

