Consider the following question from Weissman [1]
Prove that for $n \ge 1$, $F_n \equiv 4^{n-1} (2^{n} - 1) \mod 11$ for the Fibonacci sequence $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, $\ldots$
We can use induction for this and I've posted a proof below. It seems a bit lengthy and needs a couple of side results on recurrence relations for powers of 2 and 4 mod 11. I would like to ask if anyone knows of a 'cleaner' or simpler proof.
Proof using induction: The formula is true for $n=1$ and $n=2$. If we assume the relation $F_n \equiv 4^{n-1} (2^{n} - 1) \mod 11$ holds for $n \le k$.
Now use $F_{k+1} = F_{k} + F_{k-1}$ so that $F_{k+1} \equiv F_{k} + F_{k-1} \mod 11$.
Using the induction hypothesis, $$ F_{k+1} \equiv 4^{k-1} (2^{k} - 1) + 4^{k-2} (2^{k-1} - 1) \mod 11 $$ so that $$ \begin{aligned} F_{k+1} &\equiv 4^{k-2} \left( 4 (2^{k} - 1) + (2^{k-1} - 1) \right) \mod 11 \\ &\equiv 4^{k-2} \left( 4 \cdot 2^{k} - 4 + 2^{k-1} - 1 \right) \mod 11 \\ &\equiv 4^{k-2} \left( 2^{k+2} + 2^{k-1} - 5 \right) \mod 11 \end{aligned} $$
Inside the bracket above, we can use the relation (see separate proof): $$ 2^{k-1} + 2^{k} + 2^{k+2} \equiv 0 \mod 11 \quad \text{ which gives } \quad 2^{k-1} + 2^{k+2} \equiv - 2^{k} \mod 11 $$
Substituting into the earlier expression gives $$ \begin{aligned} F_{k+1} &\equiv 4^{k-2} \left( - 2^{k} - 5 \right) \mod 11 \\ &\equiv 4^{k-2} \left( 10 \cdot 2^{k} - 5 \right) \mod 11 \\ &\equiv 5 \cdot 4^{k-2} \left( 2^{k+1} - 1 \right) \mod 11 \end{aligned} $$
Now use the relation $5 \cdot 4^{k-2} \equiv 4^{k} \mod 11$ (see separate proof) to obtain $$ \begin{aligned} F_{k+1} &\equiv 4^{k} \left( 2^{k+1} - 1 \right) \mod 11 \end{aligned} $$ which shows that the formula holds for $n=k+1$ and completes the proof by induction.
Proof of $2^{k-1} + 2^{k} + 2^{k+2} \equiv 0 \mod 11 $:
$$ \begin{aligned} 2^{k-1} + 2^{k} + 2^{k+1} & \equiv 2^{k-1} (1 + 2 + 4) \mod 11 \\ & \equiv 2^{k-1} \cdot 7 \mod 11 \\ & \equiv 2^{k-1} \cdot (-4) \equiv - 2^{k+1}\mod 11 \\ \end{aligned} $$
Which gives $$ 2^{k-1} + 2^{k} + 2 \cdot 2^{k+1} \equiv 0 \mod 11 \quad \text{ i.e. } 2^{k-1} + 2^{k} + 2^{k+2} \equiv 0 \mod 11 $$
Proof of $5 \cdot 4^{k-2} \equiv 4^{k} \mod 11$: $$ \begin{aligned} 5 \cdot 4^{k-2} & \equiv - 6 \cdot 4^{k-2} \mod 11 \\ &\equiv - 3 \cdot 2 \cdot 4^{k-2} \mod 11 \\ &\equiv 8 \cdot 2 \cdot 4^{k-2} \mod 11 \\ &\equiv 16 \cdot 4^{k-2} \mod 11 \\ &\equiv 4^{k} \mod 11 \end{aligned} $$
[1]: Weissman, Illustrated Theory of Numbers (AMS)
Here is another take.
Recall Binet's formula for the Fibonacci numbers: $$ F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} $$ where $\varphi$ and $\psi$ are the roots $x^2-x-1$.
The same formula holds mod $11$ because $x^2-x-1$ does have two roots mod $11$. They are $\varphi=8$ and $\psi=4$. Therefore, $$ F_n = \frac{8^n-4^n}{8-4} = \frac{8^n-4^n}{4} = 2^{3n-2}-4^{n-1} = 4^{n-1} (2^{n} - 1) \bmod 11 $$