<s>[INST] 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?
 [/INST] *

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

</s>