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
 A: This identity is actually half of a more general identity,
$$\sum_k\binom{n-k}k2^k=\frac{(-1)^n+2^{n+1}}3\;.$$
Define a sequence $\langle a_n:n\in\Bbb N\rangle$ by
$$a_n=\frac{(-1)^n+2^{n+1}}3=\frac13(-1)^n+\frac23\cdot2^n\;.$$
This evidently satisfies a second-order homogeneous recurrence whose auxiliary polynomial has zeroes at $-1$ and $2$, so that polynomial is
$$(x+1)(x-2)=x^2-x-2\;,$$
and the recurrence is $$a_n=a_{n-1}+2a_{n-2}$$ with initial values $a_0=a_1=1$. Let 
$$f(n)=\sum_k\binom{n-k}k2^k\;;$$
certainly $f(0)=f(1)=1$. Finally, for $n\ge 2$ we have
$$\begin{align*}
f(n)&=\sum_k\binom{n-k}k2^k\\
&=\sum_k\left(\binom{n-1-k}k+\binom{n-1-k}{k-1}\right)2^k\\
&=\sum_k\binom{n-1-k}k2^k+\sum_k\binom{n-1-k}{k-1}2^k\\
&=f(n-1)+\sum_k\binom{n-1-(k+1)}k2^{k+1}\\
&=f(n-1)+2\sum_k\binom{n-2-k}k2^k\\
&=f(n-1)+2f(n-2)\;.
\end{align*}$$
Thus, the sequence $\langle f(n):n\in\Bbb N\rangle$ satisfies the same recurrence as $\langle a_n:n\in\Bbb N\rangle$ and has the same initial values, so $f(n)=a_n$ for all $n\in\Bbb N$.
A: 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}).$$
A: Here is an answer based upon a transformation of generating series.

We show the validity of the slightly more general binomial identity
\begin{align*}
\sum_{j=0}^k\binom{k-j}{j}2^j=\frac{1}{3}\left((-1)^k+2^{k+1}\right)\qquad\qquad k\geq 0\tag{1}
\end{align*}

Here we set as upper limit of the sum $j=k$ and use $\binom{p}{q}=0$ if $q>p$. We will also use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series.
Note, the sum at the LHS of (1) is of the form
\begin{align*}
  \sum_{j=0}^k\binom{k-j}{j}a_j
  \end{align*}

We can find in Riordan Array Proofs of Identities in Gould's Book by R. Sprugnoli in section 1.4 (A) a useful transformation formula:
Let $A(z)=\sum_{j=0}^\infty a_jz^j$ be a series, then the following holds
  \begin{align*}
 \frac{1}{1-z}A\left(\frac{z^2}{1-z}\right)
  =\sum_{k=0}^\infty\left(\sum_{j=0}^{k}\binom{k-j}{j}a_j\right)z^k
  \end{align*}
So, we have the following relationship
  \begin{align*}
[z^k]A(z)=a_k\qquad\longleftrightarrow\qquad
[z^k]\frac{1}{1-z}A\left(\frac{z^2}{1-z}\right)=\sum_{j=0}^{k}\binom{k-j}{j}a_j
\tag{2}\end{align*}

We obtain from (1) with $a_j=2^j$ the generating function $A(z)$
\begin{align*}
A(z)=\sum_{j=0}^\infty(2z)^j=\frac{1}{1-2z}
\end{align*}

and conclude according to (2)
  \begin{align*}
  \sum_{j=0}^k\binom{k-j}{j}2^j&=[z^k]\frac{1}{1-z}\cdot\frac{1}{1-2\frac{z^2}{1-z}}\tag{3}\\
  &=[z^k]\frac{1}{1-z-2z^2}\tag{4}\\
  &=[z^k]\left(\frac{1}{3(1+z)}+\frac{2}{3(1-2z)}\right)\tag{5}\\
  &=[z^k]\left(\frac{1}{3}\sum_{k=0}^\infty(-z)^k+\frac{2}{3}\sum_{k=0}^\infty(2z)^k\right)\tag{6}\\
  &=\frac{1}{3}\left((-1)^k+2^{k+1}\right)\tag{7}
  \end{align*}
  and the claim follows.

Comment:


*

*In (3) we apply the transformation formula (2).

*In (4) we do some simplifications.

*In (5) we apply partial fraction decomposition.

*In (6) we use the geometric series expansion.

*In (7) we select the coefficient of $z^k$.
