Proving that $\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{{n \choose 2k}\cdot 3^{n-2k}}=2^{n-1}(2^n+1) $

Question

Prove that $$\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{{n \choose 2k}\cdot 3^{n-2k}}=2^{n-1}(2^n+1)\,.$$ Can somebody help me prove this identity?

Answer 1

Note that $$ \frac{1+(-1)^k}{2} = \begin{cases} 1 &\text{if $2\mid k$} \\ 0 &\text{otherwise} \end{cases} $$ So \begin{align} \sum_{k \ge 0} \binom{n}{2k}3^{n-2k} &= \sum_{k \ge 0} \binom{n}{k}3^{n-k} \frac{1+(-1)^k}{2}\\ &= \frac{1}{2}\sum_{k \ge 0} \binom{n}{k}3^{n-k} + \frac{1}{2}\sum_{k \ge 0} \binom{n}{k}3^{n-k} (-1)^k\\ &= \frac{1}{2}(1+3)^n + \frac{1}{2}(-1+3)^n\\ &= \frac{4^n+2^n}{2} \\ &= 2^{n-1}(2^n+1) \end{align}

---

Here's an alternative proof that uses generating functions: \begin{align} \sum_{n \ge 0} \sum_{k \ge 0} \binom{n}{2k}3^{n-2k} z^n &= \sum_{k \ge 0} z^{2k} \sum_{n \ge 2k} \binom{n}{2k}(3z)^{n-2k} \\ &= \sum_{k \ge 0} z^{2k} \frac{1}{(1-3z)^{2k+1}} \\ &= \frac{1}{1-3z}\sum_{k \ge 0} \left(\frac{z}{1-3z}\right)^{2k} \\ &= \frac{1}{1-3z}\cdot\frac{1}{1-\left(\frac{z}{1-3z}\right)^2} \\ &= \frac{1-3z}{1-6z+8z^2} \\ &= \frac{1/2}{1-4z} + \frac{1/2}{1-2z} \\ &= \frac{1}{2}\sum_{n\ge 0} (4z)^n + \frac{1}{2}\sum_{n\ge 0} (2z)^n \\ &= \sum_{n\ge 0} \frac{4^n+2^n}{2} z^n \end{align} So $$\sum_{k \ge 0} \binom{n}{2k}3^{n-2k} = \frac{4^n+2^n}{2}$$