Simplifying $\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}2^{2k}$ I'm having problems with evaluating this sum:
$$\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}2^{2k}$$
A good way to simplify it would be to find some kind of combinatorial proof, but I have no idea where to search for it (my interpretations of this sum only lead to sums that are even more complicated). How to deal with such sums?
 A: Hint let :
$$\begin{align} f(x)&=\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}x^{2k}\\
 g(x)&=\sum_{k=0}^{\lfloor{\frac{n-1}{2}}\rfloor}\binom{n}{2k+1}x^{2k+1}\end{align}$$
and prove that :


*

*$f(x)+g(x)=(1+x)^n$

*$f(x)-g(x)=(1-x)^n$

A: Elaqqad’s trick solves the problem very quickly and easily and is more widely applicable than you might guess, but it’s by no means the only way to solve the problem. Since you mentioned the possibility of a combinatorial argument, here’s an approach that’s at least partly combinatorial.
Suppose that you have $n$ slips of paper numbered $1$ through $n$. Then
$$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}2^{2k}$$
is the number of ways to pick an even number of these slips, mark them with a $\times$, and then circle any subset of the marks, changing those marks to $\otimes$. This is clearly the same as the number of ways to sort the slips into three sets, unmarked, $\times$-marked, and $\otimes$-marked, in such a way that the total number of marked slips is even.
If we ignore that last condition for a moment, there are $3^n$ ways to divide the slips into the three sets. In order for the number of marked slips to be even, the number of unmarked slips must have the same parity as $n$. Thus, we’d expect to get only about $\frac{3^n}2$ acceptable divisions of the slips. Of course $\frac{3^n}2$ isn’t an integer, so this can’t be exactly right. If you were to compare calculated values of your summation with $\frac{3^n}2$ for a few values of $n$, you’d probably very quickly guess an actual closed form, which you could then try to prove by induction, but I’m going to take a different approach.
Let $g_n$ be the number of divisions of $n$ with an even number of marked slips (the good divisions) and $b_n$ the number of divisions with an odd number of marked slips (the bad division); of course $g_n+b_n=3^n$. Suppose that we start with a good division of $n$ slips. If slip $n$ is unmarked, we can throw it away and have a good division of $n-1$ slips; if it’s marked, we have a bad division of $n-1$ slips when we throw it away. Conversely, adding an unmarked slip $n$ to a good division of $n-1$ slips yields a good division of $n$ slips, while adding either kind of marked slip to a bad division of $n-1$ marked slips yields a good division of $n$ marked slips. It follows that
$$g_n=g_{n-1}+2b_{n-1}=g_{n-1}+2\left(3^{n-1}-g_{n-1}\right)=2\cdot 3^{n-1}-g_{n-1}\;,\tag{1}$$
with initial condition $g_1=1$ by inspection (or if you prefer, $g_0=1$, also by inspection). This is a straightforward first-order recurrence that is easily solved by a variety of techniques. For example, one can ‘unwind’ it:
$$\begin{align*}
g_n&=2\cdot3^{n-1}-g_{n-1}\\
&=2\cdot3^{n-1}-\left(2\cdot3^{n-2}-g_{n-2}\right)\\
&=2\cdot3^{n-1}-2\cdot3^{n-2}+g_{n-2}\\
&=2\cdot3^{n-1}-2\cdot3^{n-2}+\left(2\cdot3^{n-3}-g_{n-3}\right)\\
&=2\cdot3^{n-1}-2\cdot3^{n-2}+2\cdot3^{n-3}-g_{n-3}\\
&\;\;\vdots\\
&\overset{(*)}=2\sum_{i=1}^k(-1)^{i+1}3^{n-i}+(-1)^kg_{n-k}\\
&\;\;\vdots\\
&=2\sum_{i=1}^n(-1)^{i+1}3^{n-i}+(-1)^ng_0\\
&=2\sum_{i=0}^{n-1}(-1)^{n+1-i}3^i+(-1)^n\\
&=2(-1)^n\sum_{i=0}^{n-1}(-3)^i+(-1)^n\\
&=2(-1)^{n+1}\cdot\frac{(-3)^n-1}{-3-1}+(-1)^n\\
&=\frac{3^n-(-1)^n}2+(-1)^n\\
&=\frac{3^n+(-1)^n}2\;.\tag{2}
\end{align*}$$
Of course the step marked $(*)$ isn’t really a computation; rather, it records recognition of a pattern. Thus, it should be verified by induction that the closed form $(2)$ actually is a solution to the recurrence $(1)$ and hence is a closed form for the original summation.
