$d_n$ represents number of sequences of length $n$ made by $0, 1$ and $2$ that don't contain two consecutive 1 or 2. for example $d_2 = 7$ because valid sequences are $\{00,01,02,10,12,20,21\}$. first part of question asks to prove that $d_n = 2d_{n-1} + d_{n-2}$ and second part of question is show that
$d_n = 1 + 2 {n+1 \choose 2 } + 2^2 {n+1 \choose 4} + 2^3 {n+1 \choose 6} + ...$
I proved the first part but I don't have any idea about second part. can any one give me a hint to solving the second part of problem?
Let
$$f(n)=\sum_{\ell\ge 0}2^\ell\binom{n+1}{2\ell}\;;$$
you want to prove that $d_n=f(n)$ for all $n\ge 0$. The simplest approach is to prove it by induction on $n$. It’s easy enough to check that $d_0=f(0)$ and $d_1=f(1)$, and since the recurrence is second order, you need both of these in order to get the induction started. For the induction step, let $n>1$, and for your induction hypothesis assume that $d_k=f(k)$ for $0\le k<n$; the induction step will then consist in showing that $d_n=f(n)$. You have
$$\begin{align*} d_n&=2d_{n-1}+d_{n-2}\\ &=2f(n-1)+f(n-2)\\ &=2\sum_{\ell\ge 0}2^\ell\binom{n}{2\ell}+\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell}\\ &=\sum_{\ell\ge 0}2^{\ell+1}\binom{n}{2\ell}+\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell} \end{align*}$$
by the induction hypothesis, and you want to show that this is equal to $f(n)$, i.e., that
$$\sum_{\ell\ge 0}2^\ell\binom{n+1}{2\ell}=\sum_{\ell\ge 0}2^{\ell+1}\binom{n}{2\ell}+\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell}\;.\tag{1}$$
A natural idea is to apply Pascal’s identity a few times to reduce all of the binomial coefficients to the same upper number, $n-1$:
$$\binom{n+1}{2\ell}=\binom{n}{2\ell}+\binom{n}{2\ell-1}=\binom{n-1}{2\ell}+2\binom{n-1}{2\ell-1}+\binom{n-1}{2\ell-2}\;,$$
and
$$\binom{n}{2\ell}=\binom{n-1}{2\ell}+\binom{n-1}{2\ell-1}\;,$$
so $(1)$ is equivalent to
$$\begin{align*} \color{red}{\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell}}&+\color{blue}{2\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell-1}}+\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell-2}\\ &=\sum_{\ell\ge 0}2^{\ell+1}\binom{n-1}{2\ell}+\color{blue}{\sum_{\ell\ge 0}2^{\ell+1}\binom{n-1}{2\ell-1}}+\color{red}{\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell}}\;, \end{align*}$$
which simplifies to
$$\sum_{\ell\ge 0}2^\ell\binom{n-1}{2\ell-2}=\sum_{\ell\ge 0}2^{\ell+1}\binom{n-1}{2\ell}\;.\tag{2}$$
To complete the induction step, you need only show that $(2)$ is true: we’ve seen that it’s equivalent to $(1)$, which is what you need for the induction step.