<s>[INST] Prove a combinatoric sum: $\sum_{j=0}^{k}{{2k-j}\choose{j}}2^j=\frac{1}{3}(1+2^{2k+1})$ $$\sum_{j=0}^{k}{{2k-j}\choose{j}}2^j=\frac{1}{3}\large(1+2^{2k+1})$$
I'm 99% certain it's correct, and I also ran a first few examples with python (up to $k = 0$), but so far I haven't been able to prove it.
update:
I have tried to use induction, but going from $k$ to $k+1$ didnt work. I also tried multiplying by 3, and then splitting the sum ($rhs$) into two sums $\sum_{j=0}^{k}{{2k-j}\choose{j}}2^j + \sum_{j=0}^{k}{{2k-j}\choose{j}}2^{j+1}$. Then I tranformed the second one to $\sum_{j=1}^{k+1}{{2k-j+1}\choose{j-1}}2^j$. This would be helpfull if I could somehow calculate ${{2k-j}\choose{j}}+{{2k-j+1}\choose{j-1}}$, but I couldnt do that either.
thanks
 [/INST] Evaluating 
$$\sum_{q=0}^n {2n-q\choose q} 2^q$$
we write this as
$$\sum_{q=0}^n {2n-q\choose 2n-2q} 2^q$$
and introduce
$${2n-q\choose 2n-2q} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2q+1}} (1+z)^{2n-q} \; dz.$$
Observe that  this vanishes for $q\gt n$  so we may extend  the sum to
infinity, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n+1}} (1+z)^{2n} 
\sum_{q\ge 0} 2^q \frac{z^{2q}}{(1+z)^q}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n+1}} (1+z)^{2n} 
\frac{1}{1-2z^2/(1+z)}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n+1}} (1+z)^{2n+1} 
\frac{1}{1+z-2z^2}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n+1}} (1+z)^{2n+1} 
\frac{1}{(1+2z)(1-z)}
\; dz.$$
The residues  at the  poles sum  to zero and  we have  three potential
poles other than zero which are at $z=-1/2$, $z=1$ and $z=\infty.$ The
integral equals  the negative of the  residues at these  poles. We get
for $z=1$
$$-\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n+1}} (1+z)^{2n+1} 
\frac{1}{(1+2z)(z-1)}
\; dz$$
for a residue of
$$- 2^{2n+1} \frac{1}{3}.$$
We get for $z=-1/2$
$$\frac{1}{2} \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{2n+1}} (1+z)^{2n+1} 
\frac{1}{(1/2+z)(1-z)}
\; dz$$
for a residue of
$$\frac{1}{2} (-2)^{2n+1} \frac{1}{2^{2n+1}}
\frac{1}{3/2} = \frac{1}{3} (-1)^{2n+1} = - \frac{1}{3}.$$
Finally we have
$$\mathrm{Res}_{z=\infty}
\frac{1}{z^{2n+1}} (1+z)^{2n+1} 
\frac{1}{(1+2z)(1-z)}
\\ = - \mathrm{Res}_{z=0} \frac{1}{z^2}
z^{2n+1} \frac{(1+z)^{2n+1}}{z^{2n+1}}
\frac{1}{(1+2/z)(1-1/z)}
\\ = - \mathrm{Res}_{z=0} \frac{1}{z^2}
(1+z)^{2n+1}
\frac{1}{(1+2/z)(1-1/z)}
\\ = - \mathrm{Res}_{z=0}
(1+z)^{2n+1}
\frac{1}{(z+2)(z-1)} = 0.$$
Summing the negative of these three contributions yields
$$\frac{1}{3} 2^{2n+1} + \frac{1}{3}
= \frac{1}{3} (1+2^{2n+1}).$$
</s>