Show that $\sum\limits_{i=0}^{n/2} {n-i\choose i}2^i = \frac13(2^{n+1}+(-1)^n)$

Question

While doing a combinatorial problem, with $n$ being even, I came up with the expression

$$\sum_{i=0}^{n/2} {n-i\choose i}2^i$$

for which I used wolfram to get a closed form expression of $\dfrac{1}{3}\left(2^{n+1}+(-1)^n\right)$.

Is there an easy way to obtain this closed-form?

Also, if there are any good references for binomial coefficient identities like these I'd appreciate it. I searched some but did not find any similar to this.

Answer 1

One way is by considering generating functions.

Denoting $\displaystyle a_n = \sum_{k=0}^{n} 2^k{n-k\choose k}$

(where, we use the notation $\displaystyle \binom{n}{m} = 0$ for $m > n$)

$\displaystyle \begin{align} \sum_{n=0}^\infty a_nx^n &=\sum_{n=0}^\infty x^n\sum_{k=0}^n2^k\binom{n-k}{k} =\sum_{k=0}^\infty\sum_{n=k}^\infty2^kx^n\binom{n-k}{k}=\sum_{k=0}^\infty\sum_{n=0}^\infty2^kx^{n+k}\binom{n}{k}\\ &=\sum_{k=0}^\infty2^kx^k\frac{x^k}{(1-x)^{k+1}}=\frac{1}{1-x}\sum_{k=0}^\infty2^k\left(\frac{x^2}{1-x}\right)^k\\ &=\frac{1}{1-x}\frac{1}{1-\frac{2x^2}{1-x}}\\ &=\frac{1}{1-x-2x^2}\end{align}$

Using partial fractions to decompose:

$\displaystyle \frac{1}{1-x-2x^2} = \frac{1}{3}\left(\frac{2}{1-2x}+\frac{1}{1+x}\right) = \sum_{n=0}^{\infty} \frac{2^{n+1}+(-1)^n}{3}x^n$

Thus, $\displaystyle a_n = \frac{2^{n+1}+(-1)^n}{3}$

Answer 2

Generating functions to the rescue! \begin{align*} \sum_{\substack{n\ge 0 \\ n \text{ even}}} x^n \sum_{i=0}^{n/2} \binom{n-i}{i}2^i &= \sum_{i=0}^\infty 2^i \sum_{\substack{n\ge 2i \\ n \text{ even}}} \binom{n-i}{i} x^n \\ &= \sum_{i=0}^\infty 2^i \sum_{\substack{m\ge 0 \\ m \text{ even}}} \binom{m+i}{i} x^{m+2i} \\ &= \sum_{i=0}^\infty 2^i x^{2i} \sum_{m\ge0} \frac{1+(-1)^m}2 \binom{m+i}{i} x^m \\ &= \frac12 \sum_{i=0}^\infty (2x^2)^i \sum_{m\ge0} \binom{m+i}{i} \big( x^m + (-x)^m \big). \end{align*} Using the known series $\sum_{m\ge0} \binom{m+i}{i} x^m = (1-x)^{-(i+1)}$, we get \begin{align*} \sum_{\substack{n\ge 0 \\ n \text{ even}}} x^n \sum_{i=0}^{n/2} \binom{n-i}{i}2^i &= \frac12 \sum_{i=0}^\infty (2x^2)^i \big( (1-x)^{-(i+1)} + (1+x)^{-(i+1)} \big) \\ &= \frac1{2(1-x)} \sum_{i=0}^\infty \bigg( \frac{2x^2}{1-x} \bigg)^i + \frac1{2(1+x)} \sum_{i=0}^\infty \bigg( \frac{2x^2}{1+x} \bigg)^i \\ &= \frac1{2(1-x)} \frac1{1-2x^2/(1-x)} + \frac1{2(1+x)} \frac1{1-2x^2/(1+x)} \\ &= \frac{1-2x^2}{1-5x^2+4x^4} \\ &= \frac{2}{3 (1-4x^2)}+\frac{1}{3(1-x^2)} \\ &= \sum_{m=0}^\infty \bigg( \frac23 (4x^2)^m + \frac13 (x^2)^m \bigg) \\ &= \sum_{\substack{n\ge0 \\ n\text{ even}}} \frac{2^{n+1} + 1}3 x^n. \end{align*} Comparing coefficients of $x^n$ on both sides establishes the result (without knowing what the answer was in advance, for that matter). Note that $(-1)^n=1$ for $n$ even, so we really got the right answer.

Answer 3

Permit me to contribute a proof complex variables, for variety's sake, which is an instructive exercise.

Suppose we seek to verify that $$\sum_{q=0}^{\lfloor n/2 \rfloor} {n-q\choose q} 2^q = \frac{1}{3} \left(2^{n+1} + (-1)^n\right)$$ with $n$ a positive integer.

Introduce the integral representation $${n-q\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-q}}{z^{q+1}} \; dz$$

Note that this zero for $\lfloor n/2 \rfloor \lt q\le n$ so we may extend the sum to $n,$ getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \sum_{q=0}^n \frac{2^q}{(1+z)^q z^{q}} \; dz.$$

This is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \frac{2^{n+1}/(1+z)^{n+1}/z^{n+1}-1} {2/(1+z)/z-1} \;dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \frac{2^{n+1}/(1+z)^{n}/z^{n}-z(1+z)} {2-z(1+z)} \;dz.$$

This has two pieces, the first is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{2^{n+1}}{2-z(1+z)} \;dz \\ = \frac{2^{n+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \left(\frac{1}{3}\frac{1}{1-z} + \frac{1}{6}\frac{1}{1+z/2}\right) \; dz.$$

Extracting coefficients we find $$2^{n+1} \left(\frac{1}{3} + \frac{1}{6}\frac{(-1)^n}{2^n}\right) = \frac{1}{3} \left(2^{n+1} + (-1)^n\right).$$

The second piece is $$-\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n+1} \frac{1}{2-z(1+z)} \;dz$$ which gives a contribution of zero.

Collecting everything we obtain $$\frac{1}{3} \left(2^{n+1} + (-1)^n\right).$$