How to show this binomial equality is true/not: $\sum _{k=1}^m2^{2k-1}\binom{n}{2k-1}=\sum _{k=1}^m 2^{2k}\binom{n}{2k}$

Question

Is the above true?

For all integers $n=2m>1$ we have

$\hspace{20mm}\sum _{k=1}^m2^{2k-1}\binom{n}{2k-1}=\sum _{k=1}^m 2^{2k}\binom{n}{2k}$.

Using induction on $n=2m$ we have ; putting $m=1\implies n=2$

$2^{1}\binom{2}{1}=2^2\binom{2}{2}\implies 2=2$ which is true.

Assuming the result is true for $n=2m$ we have to prove the result for $n+2=2(m+1)$

$\sum_{k=1}^{m+1}2^{2k-1}\binom{n}{2k-1}=\sum_{k=1}^m 2^{2k-1}\binom{n}{2k-1}+2^{2m+1}\binom{n}{2m+1}$

$\hspace{35mm}=\sum _{k=1}^m 2^{2k}\binom{n}{2k}+2^{2m+1}\binom{n}{2m+1}$

I am failing to prove that

$\hspace{35mm}\sum _{k=1}^m 2^{2k}\binom{n}{2k}+2^{2m+1}\binom{n}{2m+1}=\sum _{k=1}^m 2^{2k}\binom{n}{2k}$.

Please help.

Answer 1

Proof via binomial theorem:

For any even $n$ one has:

$$\begin{array}{rl}1=1^n=((-1)+2)^n &= \sum\limits_{j=0}^n (-1)^{n-j}(2)^j\binom{n}{j}\\ &=\sum\limits_{k=0}^m(-1)^{n-2k}2^{2k}\binom{n}{2k} + \sum\limits_{k=1}^m(-1)^{n-2k-1}2^{2k-1}\binom{n}{2k-1}\\ &=2^0\binom{n}{0}+\sum\limits_{k=1}^m2^{2k}\binom{n}{2k}-\sum\limits_{k=1}^m2^{2k-1}\binom{n}{2k-1}\end{array}$$

Subtracting one from each side and moving the one summation to the other side then shows that:

$$\sum\limits_{k=1}^m 2^{2k-1}\binom{n}{2k-1} = \sum\limits_{k=1}^m2^{2k}\binom{n}{2k}$$

Going from the end of the first line to the second line, we grouped up those terms which were of even index $j$ and those which were of odd index $j$ and then reindexed them.

Moving from the second line to the third, we split off the first part of the first summation and recognized that all terms in the first summation are positive while all terms in the second were negative.

---

As for fixing your inductive proof, we make the inductive hypothesis that $\sum\limits_{k=1}^m 2^{2k-1}\binom{n}{2k-1} = \sum\limits_{k=1}^m2^{2k}\binom{n}{2k}$ is true for some $n=2m\geq 2$ and wish to show that it follows for $n+2=2(m+1)$. The base case holds as you say.

The inductive step should start however:

$$\sum\limits_{k=1}^{m+1} 2^{2k-1}\binom{n+2}{2k-1}$$

If it is not clear why we must change the $n$ as well, then try writing everything in terms of $m$ and nowere make mention of the letter $n$. Our inductive hypothesis was then $\sum\limits_{k=1}^m2^{2k-1}\binom{2m}{2k-1}=\sum\limits_{k=1}^m2^{2k}\binom{2m}{2k}$. Moving from the induction hypothesis to the inductive step, we replace all $m$'s with $(m+1)$'s.

Our inductive hypothesis is about the summation of terms of binomial coefficients multiplied by powers of two with the top being $n$, not being $n+2$... We can decrease the top by using repeated applications of Pascal's identity, but this will get messy.

$\binom{n+2}{2k-1}=\binom{n+1}{2k-1}+\binom{n+1}{2k-2} = \binom{n}{2k-1}+\binom{n}{2k-2}+\binom{n}{2k-2}+\binom{n}{2k-3}$

So, we have:

$$\begin{array}{l}\sum\limits_{k=1}^{m+1}2^{2k-1}\binom{n+2}{2k-1} = 2^{n+1}\binom{n+2}{n+1}+\sum\limits_{k=1}^m2^{2k-1}\left(\binom{n}{2k-1}+2\binom{n}{2k-2}+\binom{n}{2k-3}\right)\end{array}$$

Now... we could split the summation into three separate summations, and use the inductive hypothesis on the first... but that still leaves us with two rather ugly summations to deal with... We then would need to eventually reverse the process in order to reach the desired final representation of $\sum\limits_{k=1}^{m+1}2^{2k}\binom{n+2}{2k}$. This method, although certainly in the realm of possible, is appearing more and more to be convoluted, making the above proof relying on the binomial theorem that much more appealing due to its brevity.

Answer 2

One can also take a more combinatorial approach.

Let $S_e(n)$ be the number of ways to pick an even-sized subset $S$ of $[n]$ and an arbitrary subset $A$ of $S$; $S_e(n)$ is the number of pairs $\langle S,A\rangle$ such that $A\subseteq S\subseteq[n]$ and $|S|$ is even. Let $S_o(n)$ be the number of ways to pick an odd-sized subset $S$ of $[n]$ and an arbitrary subset $A$ of $S$; $S_o(n)$ is the number of pairs $\langle S,A\rangle$ such that $A\subseteq S\subseteq[n]$ and $|S|$ is odd. Thus, $S_e(n)+S_o(n)$ is the number of pairs $\langle A,S\rangle$ such that $A\subseteq S\subseteq[n]$, which is clearly the same as the number of triples $\langle X,Y,Z\rangle$ of pairwise disjoint subsets of $[n]$ whose union is $n$: set $A=X$ and $S=X\cup Y$. There are $3^n$ such triples, so $S_e(n)+S_o(n)=3^n$.

Let $\mathscr{S}_e(n)$ and $\mathscr{S}_o(n)$ be the sets of pairs counted by $S_e(n)$ and $S_o(n)$, respectively. For each $\langle S,A\rangle\in\mathscr{S}_e(n-1)$ there are two pairs in $\mathscr{S}_o(n)$ whose first elements contain $n$, $\langle S\cup\{n\},A\rangle$ and $\langle S\cup\{n\},A\cup\{n\}\rangle$; this accounts for all of the pairs in $\mathscr{S}_o(n)$ whose first elements contain $n$, so there are $2S_e(n-1)$ such pairs. Clearly there are $S_o(n-1)$ pairs in $\mathscr{S}_o(n)$ whose first elements do not contain $n$, so

$$S_o(n)=2S_e(n-1)+S_o(n-1)=S_e(n-1)+3^{n-1}\;.\tag{1}$$

Similarly,

$$S_e(n)=2S_o(n-1)+S_e(n-1)=S_o(n-1)+3^{n-1}\;,\tag{2}$$

and we have the recurrences

$$\begin{align*} S_o(n)&=S_o(n-2)+3^{n-1}+3^{n-2}=S_o(n-2)+4\cdot3^{n-2}\\ S_e(n)&=S_e(n-2)+3^{n-1}+3^{n-2}=S_e(n-2)+4\cdot3^{n-2} \end{align*}\tag{3}$$

with initial conditions $S_o(0)=0,S_e(0)=1,S_o(1)=2$, and $S_e(1)=1$. These recurrences are easily solved, but for the present purpose we don’t actually need the solutions. Let

$$d(n)=S_e(n)-S_o(n)\;;$$

from $(1)$ and $(2)$ we have

$$d(n)=-2d(n-1)+d(n-1)=-d(n-1)\;,$$

so $$d(n)=(-1)^nd(0)=(-1)^n\;.$$

Now let $n=2m$; then it’s clear that

$$\sum_{k=1}^m2^{2k-1}\binom{n}{2k-1}=S_o(n)\;,$$

since $2^{2k-1}\binom{n}{2k-1}$ is just the number of pairs $\langle S,A\rangle\in \mathscr{S}_o(n)$ such that $|S|=2k-1$. Similarly,

$$\sum_{k=0}^m2^{2k}\binom{n}{2k}=S_e(n)\;,$$

since $2^{2k}\binom{n}{2k}$ is the number of pairs $\langle S,A\rangle\in \mathscr{S}_e(n)$ such that $|S|=2k$, and hence

$$\sum_{k=1}^m2^{2k}\binom{n}{2k}=S_e(n)-1\;.$$

Thus,

$$\begin{align*} \sum_{k=1}^m2^{2k}\binom{n}{2k}&=S_e(n)-1\\ &=S_o(n)+d(n)-1\\ &=S_o(n)+(-1)^{2m}-1\\ &=S_o(n)\\ &=\sum_{k=1}^m2^{2k-1}\binom{n}{2k-1}\;. \end{align*}$$

More generally, we have

$$\sum_k\binom{n}{2k}2^{2k}=\sum_k\binom{n}{2k-1}2^{2k-1}+(-1)^n$$

for arbitrary $n\in\Bbb N$, where the sums are taken over $k\in\Bbb Z$ (effectively over all $k$ for which the binomial coefficient in the sum is non-zero).