Prove that $\sum_{i=0}^{\lfloor n/2 \rfloor }\sum_{j=0}^{\lfloor n/2 \rfloor-i}{n \choose 2i}{n-2i \choose 2j}2^{n-2i-2j}=4^{n-1}+2^{n-1}$

Question

I was working on problem 1 from the IMC 2020 and got the following expression for the solution:

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

The official solution is $ 4^{n-1}+2^{n-1}$. After plugging in some values and going over my solution, I determined they are equivalent. Is there an algebraic or combinatorial way to demonstrate that these two expressions are equivalent?

(IMC Problem)

Let $ n $ be a positive integer. Compute the number of words $ w $ (finite sequences of letters) that satisfy all the following three properties:

1. $ w $ consists of $ n $ letters, all of them are from the alphabet $\{a,b,c,d\}$.
2. $ w $ contains an even number of letters $ a $.
3. $ w $ contains an even number of letters $ b $.

(Problem Solution)

First, I only thought about cases where there were an even amount of one specific letter. The probability of there being $ k $ "a"s (WLOG look at $ a $) was $ Pr(k)={n \choose k} \left(\dfrac{1}{4}\right)^k \left(\dfrac{3}{4}\right)^{n-k} $.

Multiplying this by the total number of possible words $ 4^{n} $ gave $ A(k)={n \choose k} \left(3\right)^{n-k} $. To get the total even, I had to sum over whenever $ k $ was even, so

$$ \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor}A\left(2k\right)=\sum_{k=0}^{{\left\lfloor \frac{n}{2} \right\rfloor}}{n \choose 2k}3^{n-2k} $$

Next, I tried to find an equivalent function for two variables and got

$$ A\left(i,j\right)={n \choose i}{n-i \choose j}\cdot2^{n-i-j} $$

because there are $ n $ spots for the first $ i $ letters to go, $ n-i $ spots for the next $ j $, and there are 2 possible letters for each other spot (with $ n-i-j $ other spots).

Now, I needed to sum all possible even combinations. The first thing I thought of was

$$ \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}A\left(2i,2j\right) $$

but this counts impossible cases, so I had to limit $ j $ so that the maximum sum was less than $ n $ and got

$$ \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor-i}A\left(2i,2j\right) $$

or

$$ \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor-i}{n \choose 2i}{n-2i \choose 2j}2^{n-2i-2j} $$

Update

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

Factor

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

Now looking at the second sum, replace $ n-2i $ with $ k $ to get

$$ \sum_{j=0}^{k}{k \choose 2j}2^{k-2j} $$

which equals $ \frac{3^{k}+1}{2} $. Plugging back in gives

$$ \sum_{i=0}^{n}{n \choose 2i}\frac{3^{n-2i}+1}{2} $$ After distributing, you have

$$ \frac{1}{2}\sum_{i=0}^{n}{n \choose 2i}*3^{n-2i}+\frac{1}{2}\sum_{i=0}^{n}{n \choose 2i} $$

Simplifying to

$$ \frac{1}{2}\sum_{i=0}^{n}{n \choose 2i}3^{n-2i}+2^{n-2} $$

If someone can help me solve that first sum, I believe the proof will be complete.

Answer 1

Supposing we start from

$$\sum_{p=0}^n \frac{1}{2} (1+(-1)^p) \sum_{q=0}^{n-p} \frac{1}{2} (1+(-1)^q) {n\choose p} {n-p\choose q} 2^{n-p-q} = 4^{n-1} + 2^{n-1}.$$

This is

$$\sum_{p=0}^n (1+(-1)^p) {n\choose p} \sum_{q=0}^{n-p} (1+(-1)^q) {n-p\choose q} 2^{n-p-q} = 4^n + 2^{n+1}.$$

The LHS becomes

$$\sum_{p=0}^n (1+(-1)^p) {n\choose p} 2^{n-p} \sum_{q=0}^{n-p} (1+(-1)^q) {n-p\choose q} 2^{-q} \\ = \sum_{p=0}^n (1+(-1)^p) {n\choose p} 2^{n-p} ((3/2)^{n-p}+(1/2)^{n-p}) \\ = \sum_{p=0}^n (1+(-1)^p) {n\choose p} (3^{n-p}+1^{n-p}).$$

We obtain

$$4^n + 2^n + 2^n + 0 = 4^n + 2^{n+1}$$

as claimed.

Answer 2

Problem Statement

Let’s do a minor change to the problem statement: instead of using alphabets $\{a,b,c,d\}$ we use $\{a,b,c,e\}$. Same condition, we want even numbers of $a$ and $b$.

Calculation

First, we choose $m$ vowels and $n-m$ consonants. The number of possibilities is

$$ \binom{n}{m} \phantom{x} \forall \phantom{x} m\in [0,n] $$

Then, we select an even number of vowels to be $a$. The number of possibilities is

$$ 2^{m-1} $$

if $m$ is nonzero or $1$ if $m=0$. Then we select an even number of consonants to be $b$. The number of possibilities is

$$ 2^{n-m-1} $$

if $m\neq n$ and $1$ if $m=n$.

Results

The number of possibilities is given by the following:

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

Substitute $\sum_{m=1}^{n-1}\binom{n}{m}=2^{n}-2$, do some algebra, then you will get $4^{n-1}+2^{n-1}$