<s>[INST] How to prove $\sum_{k=0}^{n}2^{2k}\binom{2n}{2k}=\frac{9^{n}+1}{2}$ by using mathematical induction? My question is how to prove $\sum_{k=0}^{n}2^{2k}\binom{2n}{2k}=\frac{9^{n}+1}{2}$ by using mathematical induction?
I can finish this question by considering the binomial $(1-x)^{2n}$. First, prove that
$$\binom{2n}{0}+\binom{2n}{2}(2)^{2}+\binom{2n}{4}(2)^{4}+\dots+\binom{2n}{2n}(2)^{2n}\\=\binom{2n}{0}+\binom{2n}{1}(2)+\binom{2n}{3}(2)^{3}+\dots+\binom{2n}{2n-1}(2)^{2n-1}$$ by taking $x=2$.
Then, I can prove $\sum_{k=0}^{n}2^{2k}\binom{2n}{2k}=\frac{9^{n}+1}{2}$ by taking $x=-2$.
When I ask to prove this question by using mathematical induction, I can prove that $P(0)$ is true. However, I am stuck in how to use the hypothesis of $P(a)$ is true for some positive integer $a$ to prove $P(a+1)$ is true.
Since I think that it is not correct that using the way which is similar to the above method (considering the binomial $(1-x)^{2a+2}$) to prove the $P(a+1)$ is true (As we need to prove $P(a+1)$ is true if $P(a)$ is true, if we use this way to do then we have ignored the hypothesis of $P(a)$ is true).
May anyone give me some suggestions to finish this question by mathematical induction? Thank you so much.
 [/INST] Use Pascal’s identity twice to get the identity
$$\binom{n}k=\binom{n-2}{k-2}+2\binom{n-2}{k-1}+\binom{n-2}k\,,$$
and then use that at the start of the induction:
$$\begin{align*}
\sum_{k=0}^{n+1}2^{2k}\binom{2n+2}{2k}&=\sum_{k=0}^{n+1}2^{2k}\left(\binom{2n}{2k-2}+2\binom{2n}{2k-1}+\binom{2n}{2k}\right)\\
&=\sum_{k=1}^{n+1}2^{2k}\binom{2n}{2k-2}+2\sum_{k=1}^n2^{2k}\binom{2n}{2k-1}\\
&\qquad+\sum_{k=0}^n2^{2k}\binom{2n}{2k}\\
&=4\sum_{k=0}^n2^{2k}\binom{2n}{2k}+4\sum_{k=1}^n2^{2k-1}\binom{2n}{2k-1}+\frac{9^n+1}2\\
&=5\left(\frac{9^n+1}2\right)+4\left(\sum_{k=0}^{2n}2^k\binom{2n}k-\frac{9^n+1}2\right)\\
&=5\left(\frac{9^n+1}2\right)+4\left(3^{2n}-\frac{9^n+1}2\right)\\
&=4\cdot9^n+\frac{9^n+1}2\\
&=\frac{9\cdot9^n+1}2\\
&=\frac{9^{n+1}+1}2\,.
\end{align*}$$
</s>