identities and binomial coefficients 
I'm having some problems proving this identity. I tried using some formulas I found on the internet so I can turn that $2$ base number into something else but i'm not really sure how to do that. I would be really thankful if someone could help!
 A: We rewrite the first sum as follows
$$
\eqalign{
  & \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{  m + k \cr   k \cr}  \right)2^{\,n - k} }
  = \sum\limits_{\left( {0\, \le } \right)\,k\, \le \,n} {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n - k} \right)}
  {\left( \matrix{  m + k \cr  k \cr}  \right)\left( \matrix{  n - k \cr   j \cr}  \right)1^{\,n - k - j} 1^{\,j} } }  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\sum\limits_{0\, \le \,j\,\left( { \le \,n - k} \right)}
  {\left( \matrix{  m + k \cr  k \cr}  \right)\left( \matrix{  n - k \cr   n - k - j \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\,\left( { \le \,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)}
  {\left( \matrix{  m + k \cr  k \cr}  \right)\left( \matrix{  n - k \cr   n - k - j \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\,\left( { \le \,n} \right)} {\left( \matrix{  m + n + 1 \cr   n - j \cr}  \right)}
  = \sum\limits_{\left( {0\, \le } \right)\,j\, \le \,n} {\left( \matrix{  m + n + 1 \cr   j \cr}  \right)}  =  \quad \quad (*)  \cr 
  &  = 2^{\,m + n + 1}  - \sum\limits_{n + 1\, \le \,j\,\left( { \le \,n + m + 1} \right)} {\left( \matrix{  m + n + 1 \cr   j \cr}  \right)}  =   \cr 
  &  = 2^{\,m + n + 1}  - \sum\limits_{n + 1\, \le \,j\,\left( { \le \,n + m + 1} \right)} {\left( \matrix{  m + n + 1 \cr   m + n + 1 - j \cr}  \right)}  =   \cr 
  &  = 2^{\,m + n + 1}  - \sum\limits_{0\, \le \,j\,\left( { \le \,m} \right)} {\left( \matrix{  m + n + 1 \cr   m - j \cr}  \right)}  =   \cr 
  &  = 2^{\,m + n + 1}  - \sum\limits_{\left( {0\, \le } \right)\,j\, \le \,m} {\left( \matrix{  m + n + 1 \cr   j \cr}  \right)}  \cr} 
$$
and since the second sum is  the first with $m,n$ exchanged,
the identity clearly follows by comparing line (*) with the last line.
Note:   


*

*the line (*) follows from the above through the "Double Convolution" formula
$$
\sum\limits_k {\left( \matrix{  a + k \cr   n + k \cr}  \right)\left( \matrix{  b - k \cr   m - k \cr}  \right)}
  = \left( \matrix{  a + b + 1 \cr   n + m \cr}  \right)
$$

*the summation bounds put in brackets are those which are
superfluous, since they are implicit in the binomial.
A: We have by inspection that
$$\sum_{k=0}^n {m+k\choose k} 2^{n-k}
= 2^n [z^n] \frac{1}{1-z} \frac{1}{(1-z/2)^{m+1}}.$$
This is
$$2^n \times \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\frac{1}{1-z} \frac{1}{(1-z/2)^{m+1}}
\\ = - 2^n  \times \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\frac{1}{z-1} \frac{2^{m+1}}{(2-z)^{m+1}}
\\ = 2^{n+m+1} (-1)^{m} \times \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\frac{1}{z-1} \frac{1}{(z-2)^{m+1}}.$$
With
$$f(z) = 2^{n+m+1} (-1)^{m} \frac{1}{z^{n+1}}
\frac{1}{z-1} \frac{1}{(z-2)^{m+1}}$$
we will be using the fact that residues sum to zero i.e.
$$\mathrm{Res}_{z=0} f(z)
+ \mathrm{Res}_{z=1} f(z)
+ \mathrm{Res}_{z=2} f(z)
+ \mathrm{Res}_{z=\infty} f(z) = 0.$$
The  residue at  infinity is  zero since  $\lim_{R\to\infty} 2\pi  R /
R^{n+1} / R / R^{m+1} = 0.$
The residue at one is
$$2^{n+m+1} (-1)^{m} \times (-1)^{m+1} = - 2^{n+m+1}.$$
For the residue at two we use the Leibniz rule:
$$\frac{1}{m!} \left( \frac{1}{z^{n+1}}
\frac{1}{z-1} \right)^{(m)}
\\ = \frac{1}{m!} \sum_{k=0}^m {m\choose k}
(-1)^k \frac{(n+k)!}{n!} \frac{1}{z^{n+1+k}}
(-1)^{m-k} \frac{(m-k)!}{(z-1)^{m-k+1}}
\\ =  (-1)^m \sum_{k=0}^m {n+k\choose k}
\frac{1}{z^{n+1+k}} \frac{1}{(z-1)^{m-k+1}}.$$
Restore factor in front and evaluate at $z=2$:
$$2^{n+m+1} (-1)^{m} \times
(-1)^m \sum_{k=0}^m {n+k\choose k}
\frac{1}{2^{n+1+k}}
= \sum_{k=0}^m {n+k\choose k} 2^{m-k}.$$
Summing the residues we have shown that
$$\bbox[5px,border:2px solid #00A000]{
\sum_{k=0}^n {m+k\choose k} 2^{n-k}
+ \sum_{k=0}^m {n+k\choose k} 2^{m-k}
- 2^{n+m+1} = 0} $$
which is the claim.
Remark. This is  a special case of an identity  by Gosper which
was         proved        at         the        following         MSE
link (set $x=1/2.$) 
Addendum.  The  initial  step  may be  done  using  an  Iverson
bracket.  We have
$$\sum_{k=0}^n {m+k\choose k} 2^{n-k}
= \sum_{k\ge 0} {m+k\choose k} 2^{n-k} [[0\le k\le n]]
\\ = \sum_{k\ge 0} {m+k\choose k} 2^{n-k}
[z^n] \frac{z^k}{1-z}
= [z^n] \frac{1}{1-z} \sum_{k\ge 0} {m+k\choose k} 2^{n-k} z^k
\\ = 2^n [z^n] \frac{1}{1-z} \sum_{k\ge 0} {m+k\choose k} 2^{-k} z^k
= 2^n [z^n] \frac{1}{1-z}  \frac{1}{(1-z/2)^{m+1}}.$$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\ds{\bbox[10px,#ffd]{\sum_{k = 0}^{n}{m + k \choose k}2^{n - k} +
\sum_{k = 0}^{m}{n + k \choose k}2^{m - k} = 2^{m + n + 1}}:\ {\LARGE ?}} $

\begin{equation}
\mbox{Lets}\ \mrm{f}_{mn}\pars{x} \equiv
\sum_{k = 0}^{n}{m + k \choose k}\,x^{k}\,,\qquad
\left\{%
\begin{array}{rcl}
\ds{\mrm{f}\pars{0}} & \ds{=} & \ds{1}
\\[2mm]
\ds{2^{n}\,\mrm{f}_{mn}\pars{1 \over 2} +
2^{m}\,\mrm{f}_{nm}\pars{1 \over 2}}  & \ds{=} & {\LARGE ?}
\end{array}\right.\label{1}\tag{1}
\end{equation}

\begin{align}
\mrm{f}_{mn}\, '\pars{x} & =
\sum_{k = 1}^{n}{\pars{m + k}! \over \pars{k - 1}!\,m!}\,x^{k - 1} =
\sum_{k = 0}^{n - 1}{\pars{m + k + 1}! \over k!\,m!}\,x^{k}
\\[5mm] & =
\sum_{k = 0}^{n - 1}\pars{m + k + 1}{m + k \choose k}\,x^{k}
\\[5mm] & =
-\pars{m + n + 1}{m + n \choose n}x^{n} +
\pars{m + 1}\sum_{k = 0}^{n}\,{m + k \choose k}\,x^{k}
\\[2mm] &
+ x\,\totald{}{x}\sum_{k = 0}^{n}\,{m + k \choose k}\,x^{k}
\\[5mm] & =
-\pars{m + n + 1}{m + n \choose n}x^{n} +
\pars{m + 1}\mrm{f}_{mn}\pars{x} + x\,\mrm{f}_{mn}\, '\pars{x}
\end{align}
Then, I got a first order differential equation for
$\ds{\mrm{f}_{mn}\pars{x}}$. Namely,
$$
\mrm{f}_{mn}\, '\pars{x} + {m + 1 \over x - 1}\,\mrm{f}\pars{x} = 
\pars{m + n + 1}{m + n \choose n}\,{x^{n} \over x - 1}
$$
Multiply both members by the integrating factor
$\ds{\pars{x - 1}^{m + 1}}$:
\begin{align}
&\pars{x - 1}^{m + 1}\mrm{f}_{mn}\, '\pars{x} +
\pars{m + 1}\pars{x - 1}^{m}\,\mrm{f}_{mn}\pars{x}
\\[2mm] = &\ 
\pars{m + n + 1}{m + n \choose n}\,x^{n}\pars{x - 1}^{m}
\end{align}
which is equivalent to
$$
\totald{\bracks{\pars{x - 1}^{m + 1}\mrm{f}_{mn}\pars{x}}}{x} = 
\pars{m + n + 1}{m + n \choose n}\,x^{n}\pars{x - 1}^{m}
$$
Integrate both members over $\ds{\pars{0,1/2}}$:
\begin{align}
&\pars{-1}^{m + 1}\, 2^{-m - 1}\,\mrm{f}_{mn}\pars{1 \over 2} -
\pars{-1}^{m + 1}\
\overbrace{\mrm{f}_{mn}\pars{0}}^{\ds{=\ 1}}\
\\[2mm] = &\
\pars{-1}^{m}\pars{m + n + 1}{m + n \choose n}
\int_{0}^{1/2}x^{n}\pars{1 - x}^{m}\,\dd x
\\[5mm] &\
\mbox{which yields}
\\[2mm]
&\mrm{f}_{mn}\pars{1 \over 2} = 2^{m + 1}
\\[2mm] &\
- 2^{m + 1}\pars{m + n + 1}
{m + n \choose n}\int_{0}^{1/2}x^{n}\pars{1 - x}^{m}\,\dd x
\end{align}
The $\ds{\underline{final\ solution}}$
$\ds{\left(\vphantom{\large A}\right.}$ see (\ref{1})
$\ds{\left.\vphantom{\large A}\right)}$ becomes:
\begin{align}
&\phantom{+\,\,\,}\bracks{2^{n + m + 1} - 2^{n + m + 1}\pars{m + n + 1}
{m + n \choose n}\int_{0}^{1/2}x^{n}\pars{1 - x}^{m}\,\dd x}
\\[2mm] &\ +
\bracks{2^{m + n + 1} - 2^{m + n + 1}\pars{n + m + 1}
{n + m \choose m}
\color{red}{\int_{0}^{1/2}x^{m}\pars{1 - x}^{n}\,\dd x}}
\end{align}
Under the change $\ds{x \mapsto 1 - x}$, the
$\ds{\color{red}{last\ integral}}$ becomes equal to
$\ds{\int_{1/2}^{1}x^{n}\pars{1 - x}^{m}\,\dd x}$ such that the $\ds{\underline{final\ solution}}$ is reduced to:
\begin{align}
&2 \times2^{n + m + 1}
- 2^{n + m + 1}\pars{m + n + 1}
{m + n \choose n}\int_{0}^{1}x^{n}\pars{1 - x}^{m}\,\dd x
\\[5mm] = &\
2 \times2^{n + m + 1}
- 2^{n + m + 1}\pars{m + n + 1}{m + n \choose n}\
\underbrace{\Gamma\pars{n + 1}\Gamma\pars{m + 1} \over
\Gamma\pars{n + m + 2}}
_{\ds{=\ {1 \over \pars{m + n + 1}{m + n \choose n}}}}
\\[5mm] = &\
2 \times 2^{n + m + 1} - 2^{n + m + 1} \times 1 =\
\bbox[15px,#ffd,border:1px groove navy]{\Large 2^{m + n + 1}} \\ &
\end{align}
