<s>[INST] Proving combinatorial formula by induction and combinatorially I need to prove this equation by induction and by combinatorial explanation. $$\sum_{k=0}^{n} \left( \begin{array}{c} 4n \\ 4k \end{array} \right) = 2^{4n-2} + (-1)^n \cdot 2^{2n-1}$$
My induction proof:
Base case: p(1): $$\left( \begin{array}{c} 4 \\ 0 \end{array} \right) + \left( \begin{array}{c} 4 \\ 4 \end{array} \right) = 2^{4*1-2} + (-1)^1 \cdot 2^{2*1-1}\;\;\;\;\;\;\;\checkmark$$
Inductive step: $p(k) \Longrightarrow p(k+1)$: $$\sum_{k=0}^{n} \left( \begin{array}{c} 4n \\ 4k \end{array} \right) + \left( \begin{array}{c} 4(n+1) \\ 4k \end{array} \right) = 2^{4n-2} + (-1)^n \cdot 2^{2n-1} + \left( \begin{array}{c} 4(n+1) \\ 4k \end{array} \right) \\ \sum_{k=0}^{n} \left( \begin{array}{c} 4(n+1) \\ 4(k+1) \end{array} \right) = 2^{4n-2} + (-1)^n \cdot 2^{2n-1} + \left( \begin{array}{c} 4(n+1) \\ 4k \end{array} \right)$$
I got stuck in this part and I can't find a combinatorial explanation to prove this.
 [/INST] The problem is that the $n+1$ case isn't actually obtained from the $n$ case by adding an extra term to the end, the way you're thinking of it.
Here are the first few cases of this formula:

*

*For $n=1$, $\binom 40 + \binom 44 = 2^2 - 2^1$.

*For $n=2$, $\binom 80 + \binom 84 + \binom 88 = 2^6 + 2^3$.

*For $n=3$, $\binom{12}0 + \binom{12}{4} + \binom{12}{8} + \binom{12}{12} = 2^{10} - 2^5$.

*For $n=4$, $\binom{16}{0} + \binom{16}{4} + \binom{16}{8} + \binom{16}{12} + \binom{16}{16} = 2^{14} + 2^7$.

To prove this by induction, you might use Pascal's formula: $\binom nk = \binom{n-1}{k-1} + \binom{n-1}{k}$. But then you have to look at some intermediate cases as well: sums where the tops and/or the bottoms of the binomial coefficients aren't multiples of $4$. It's possible to get there, but the binomial theorem argument suggested in the comments is easier.
</s>