Fibonacci

F_m+n = F_m-1F_n + F_mF_n+1

Bewijs 1:
Als
dan is met volledige inductie eenvoudig aan te tonen dat
Dan is Mⁿ⁺¹Mⁿ = M²ⁿ⁺¹
Vermenigvuldig de twee linker matrices met elkaar en vergelijk het (1,1) element van beide leden.

Bewijs 2:
Met volledige inductie naar n.
Voor n=0 staat er (want F₀ = 0) F_m = F_m en dat is triviaal.
Voor n=1 staat er F_m+1 = F_m-1 + F_m en dat is per definitie juist.
Stel de formule is juist voor n=k met k≥1, dan moeten we aantonen dat F_m+k+1 = F_m-1F_k+1 + F_mF_k+2
Nu is F_m-1F_k+1 + F_mF_k+2 = F_m-1(F_k+F_k-1) + F_m(F_k+1+F_k) =
= F_m-1F_k + F_mF_k+1 + F_m-1F_k-1 + F_mF_k = (F_m-1F_k + F_mF_k+1) + (F_m-1F_k-1 + F_mF_k) =
(volgens de inductiehypothese) F_m+k + F_m+k-1 = F_m+k+1
en de formule is dus ook juist voor n=k+1 en dientengevolge voor alle n≥0.