Prove a combinatoric sum: $\sum_{j=0}^{k}{{2k-j}\choose{j}}2^j=\frac{1}{3}(1+2^{2k+1})$

Question

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

Answer 1

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

Answer 2

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}).$$

Answer 3

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