Prove the following recurrence: $F_{2n+1}=3F_{2n-1}-F_{2n-3}$ Prove the following identity:
$$F_{2n+1}=3F_{2n-1}-F_{2n-3}$$
So far I know that $F_n=F_{n-1}-F_{n-2}\implies F_{2n+1}=F_{2n}+F_{2n-1}$
Just not sure where to go from here to get to the conclusion.
Note: $F_i$ is the $i^{\textrm{th}}$ term of the Fibonacci sequence with $F_0=0, F_1=F_2=1$.
 A: Given that the sequence $\{F_n\}_{n\in\mathbb{N}}$ has a characteristic polynomial $p(x)=x^2-x-1$ with roots $\phi,\bar{\phi}$, then both the sequences $\{F_{2n}\}_{n\in\mathbb{N}}$ and $\{F_{2n+1}\}_{n\in\mathbb{N}}$ have a characteristic polynomial with roots $\phi^2=1+\phi,\bar{\phi}^2=1+\bar\phi$, hence the characteristic polynomial of $\{F_{2n+1}\}_{n\in\mathbb{N}}$ is $p(x-1)=x^2-3x+1$ from which it follows that:
$$ F_{2n+5} = 3 F_{2n+3}-F_{2n+1}. \tag{1}$$
It is sufficient to check that $(1)$ holds for $n=0,1$ in order that it holds for every $n$ by induction.
If you're still unsatisfied, notice that $(1)$ is equivalent to:
$$ F_{2n+4} = 2 F_{2n+3}-F_{2n+1} = F_{2n+3} + F_{2n+2} \tag{2}$$
that is pretty straightforward.
A: Using the recurrence $F_{k+1} = F_k + F_{k-1}$ twice we find
\begin{align}F_{2n+1} &= F_{2n} + F_{2n-1} \\
&\underset{(1)}{=} F_{2n-1} + F_{2n-2} + F_{2n-1}\\
&= 2F_{2n-1} + F_{2n-2}\\
&\underset{(2)}{=} 2F_{2n-1} + F_{2n-1} - F_{2n-3}\\
&= 3F_{2n-1} - F_{2n-3}.
\end{align}
The recurrence was used in $(1)$ and $(2)$.
