Let $u_{n}$ be the sequence defined by $u_{1}=4, u_{2}=9$ and then $u_{n}=3 u_{n-1}-u_{n-2}-2 \cdot(-1)^{n}$. Find $u_{n}$.
By calculating the first terms of the sequence, we find 4, 9, 25, $64, \ldots$ We recognize the squares of the first terms of the Fibonacci sequence. We will prove that $u_{n}=F_{n+2}^{2}$. This relation is correct for the first terms.

$3 F_{n-1}^{2}-F_{n-2}^{2}-2(-1)^{n}=2\left(F_{n-1}^{2}+(-1)^{n+1}\right)+F_{n-1}^{2}-F_{n-2}^{2}=2 F_{n} F_{n-2}+F_{n-1}^{2}-F_{n-2}^{2}$, where the last line comes from exercise 4. $2 F_{n} F_{n-2}+F_{n-1}^{2}-F_{n-2}^{2}=-F_{n}^{2}+2 F_{n} F_{n-2}-F_{n-2}^{2}+$ $F_{n-1}^{2}+F_{n}^{2}=-(F_{n}-F_{n-2})^{2}+F_{n-1}^{2}+F_{n}^{2}=F_{n}^{2}$, so $F_{n+2}$ indeed satisfies the correct recurrence, which concludes the proof.