\sum^{m+1}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}=\sum^{m}_{k=0}\frac{1}{2^k}{{m+1+k}\choose k}+\frac{1}{2^{m+1}}{{2m+2}\choose {m+1}}=2^{m+1}-{{2m+2}\choose {m+1}}+{{2m+2}\choose {m+1}}=2^{m+1}