0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.

Stim ca <tex>M_{i}</tex> este egal cu <tex>Z \times M_{i-1}</tex> si mai stim ca <tex>M_{i-1}</tex> este egal cu <tex>Z \times M_{i-2}</tex>. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca <tex>M_{i}</tex> este egal cu <tex>Z^2 \times M_{i-2}</tex>. Inductiv rezulta ca <tex>M_{i}</tex> = <tex>Z^{N-1} \times M_{1}</tex>. 'Soluţia':/job_detail/372680?action=view-source optima se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, avand complexitatea finala de $O(log K * CONST)$. $CONST$ este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a $3$-a, adica $8$.

Stim ca <tex>M_{i}</tex> este egal cu <tex>Z \times M_{i-1}</tex> si mai stim ca <tex>M_{i-1}</tex> este egal cu <tex>Z \times M_{i-2}</tex>. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca <tex>M_{i}</tex> este egal cu <tex>Z^2 \times M_{i-2}</tex>. Inductiv rezulta ca <tex>M_{i}</tex> = <tex>Z^{N-1} \times M_{1}</tex>. 'Soluţia':/job_detail/372680?action=view-source optima se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, avand complexitatea finala de <tex>O(log K \times CONST)</tex>. <tex>CONST</tex> este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a <tex>3</tex>-a, adica <tex>8</tex>.

h2. Aplicaţii