My problem relies on an earlier recursive definition that we solved in class:
$W_n = 3W_{n-1}- W_{n-2}$ if $n \ge 2, W_0=1$, and $W_1=3.$
It also recalls the Fibonacci recursive definition of $F_n = F_{n-1} + F_{n-2}$ if $n \ge 3, F_1\ge 1$, and $F_2 \ge 1$.
The problem asks me to prove by induction that $W_n\ge F_{2n+2}$ $\forall n \ge 0$.
For the base case, I checked $W_2 = 3W_1 - W_0 = 3\times3 - 1 = 8 = F_6$, which works out.
I'm not sure about what the induction step should be in this case. I know that I have to get to $W_{n+1} \ge F_{2(n+1)+2}$.
I'm thinking maybe I set up $W_{n+1} = 3W_n - W_{n-1}$ and try to translate the right into Fibonacci numbers. I haven't been able to find any induction problems that deal with the relationship between two difference recursive equations like this.
Thanks!
We have $F_n = a \alpha^n + b \beta^n$, for some $a,b \in \mathbb R$, and $\alpha,\beta$ the roots of $X^2-X-1$. (Their precise value is not really important here, but see Binet's formula.)
Then $F_{2n}=a (\alpha^2)^n + b (\beta^2)^n$. Now, $\alpha^2,\beta^2$ are the roots of $X^2-3X+1$ because $\alpha^2+\beta^2=(\alpha+\beta)^2-2\alpha\beta=1+2=3$ and $\alpha^2\beta^2=(\alpha\beta)^2=1$.
Therefore, $G_n=F_{2n}$ satisfies the recurrence $G_n = 3G_{n-1}- G_{n-2}$, the same recurrence as your $W_n$. Since $W_0=G_1$ and $W_1=G_2$, we have $W_n=G_{n+1}=F_{2n+2}$ for all $n$.