How do I solve this problem based on induction? Let $a_0 = 0, a_1 = 1$ and $ a_k = a_{k-1} + a_{k-2}$ for $n \ge 3$. Let $b_0 = 2, b_1 = 1$ and $b_n = a_{n+2} - a_{n-2}$. Prove by induction that $a_{2n} = a_nb_n$.
For $n=1$, $a_2 = 1$ and $a_1b_1=1$.
For $n=2$, $a_4 = 3$ and $a_2b_2=3$.
Let's assume it to be true for $n=k-1$ and $n=k$
Then $a_{2k-2} = a_{k-1}b_{k-1}$
and $a_{2k} = a_{k}b_{k}$
$=> a_{2k-2} + a_{2k-1} = a_{k}b_{k}$
$=> a_{k-1}b_{k-1} + a_{2k-1} = a_{k}b_{k}$
$=> a_{2k-1} = a_{k}b_{k}-a_{k-1}b_{k-1}  $
$=> 2a_{2k} + a_{2k-1} = 3a_{k}b_{k}-a_{k-1}b_{k-1}  $
$=> 2a_{2k} + a_{2k-1} = 3a_{k}b_{k}-a_{k-1}b_{k-1}  $
$=> a_{2k} + a_{2k+1} = 3(a_{k+1}-a_{k-1})(a_{k+2}-a_{k-2})-a_{k-1}(a_{k+1}-a_{k-3})  $
$=> a_{2k+2} = 3(a_{k+1}-a_{k-1})(a_{k+3}-a_{k+1}-a_{k-1}+a_{k-3})-a_{k-1}a_{k+1}+a_{k-1}a_{k-3}  $
$=> a_{2k+2} =2a_{k+1}a_{k+3} - 3(a_{k+1})^2 +3a_{k+1}a_{k-3} - 3a_{k-1}a_{k+3} + 3(a_{k-1})^2 - 2a_{k-1}a_{k-1} +a_{k+1}a_{k+3} - a_{k+1}a_{k-1}$
$=> a_{2k+2} =2a_{k+1}a_{k+3} - 3(a_{k+1})^2 +3a_{k+1}a_{k-3} - 3a_{k-1}a_{k+3} + 3(a_{k-1})^2 - 2a_{k-1}a_{k-1} +a_{k+1}(a_{k+3} - a_{k-1})$
$=> a_{2k+2} =2a_{k+1}a_{k+3} - 3(a_{k+1})^2 +3a_{k+1}a_{k-3} - 3a_{k-1}a_{k+3} + 3(a_{k-1})^2 - 2a_{k-1}a_{k-1} +a_{k+1}b_{k+1}$
I have to prove here that $$2a_{k+1}a_{k+3} - 3(a_{k+1})^2 +3a_{k+1}a_{k-3} - 3a_{k-1}a_{k+3} + 3(a_{k-1})^2 - 2a_{k-1}a_{k-1} = 0$$
I hope there is an easier method than this.

Indeed there is a simple method. Denote $c_n=a_{2n} -a_nb_n$ and we want to prove that $c_n=0$ for all $n$. The first thing we want to prove is that $$c_{n+2}=3c_{n+1}-c_n,$$ for which no induction is needed. For example, we only need to show any of $a_{2n}$, $a_{n-2}a_n$ satisfies the recursion. For $a_{2n}$, we want to show $$a_{2n+4} = 3a_{2n+2} - a_{2n},$$ or even simpler $$a_{k+4}=3a_{k+2}-a_k$$ and we can just plug in the recursive relationship for $a_n$ and prove this easily.
Then next we need to show $c_0=c_1=0$ and then prove $c_n=0$ by induction. 
