Question on calculating a Fibonacci Number using Matrix Exponentiation We know that $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k = \begin{pmatrix}F_{k + 1} & F_k \\ F_k & F_{k - 1}\end{pmatrix},$ of which there is a simple proof by induction. However, since matrix multiplication is associative, we should be able to split $k$ into $a + b$ so that,
$$ \begin{pmatrix}F_{a + 1} & F_a \\ F_a & F_{a - 1}\end{pmatrix} \begin{pmatrix}F_{b + 1} & F_b \\ F_b & F_{b - 1}\end{pmatrix} = \begin{pmatrix}F_{k + 1} & F_k \\ F_k & F_{k - 1}\end{pmatrix} .$$
The matrix multiplication gives,
$$ \begin{pmatrix}F_{a+1}F_{b+1} + F_aF_b & F_{a+1}F_b + F_aF_{b-1} \\ F_aF_{b+1} + F_{a-1}F_b & F_aF_b + F_{a-1}F_{b-1} \end{pmatrix}.$$
Is there a proof using more elementary Fibonacci identities that this is equal to $\begin{pmatrix}F_{k + 1} & F_k \\ F_k & F_{k - 1}\end{pmatrix}?$
 A: I can't honestly call this proof "more elementary" than the proof you've given in the question because I find that proof to be quite elementary, but perhaps you'll find it more palatable.
Decomposing sequences defined by linear recurrences:
Let $A_k, B_k$ denote two sequences that satisfy the same recursive relation as $F_k$ but with the initial conditions $A_2 = B_1 = 1, A_1=B_2 = 0$.
Then for any $a$, the sequence $G_k = F_{a+1}A_k + F_aB_k$ satisfies
$G_{k+1} = G_k + G_{k-1}$, $G_2 = F_{a+1}$ and $G_1 = F_a$, so that $G_k = F_{k+a-1}$.  That is, we've shown
$$F_{k+a-1} = F_{a+1}A_k+F_aB_k$$
Now we consider the identity of the $A,B$ sequences:

*

*$A$ satisfies the defining recurrence for the Fibonacci sequence.  Also,  $A_2 = 1=F_1$ and $A_3 = A_2+A_1 = 1+0  = 1=F_2$.  That is, $A$ is just a re-indexed Fibonacci sequence, specifically $A_k = F_{k-1}$.

*$B$ satisfies the defining recurrence for the Fibonacci sequence.  Also, $B_3 = B_2+B_1 = 0+1=F_1$ and $B_4 = B_3+B_2 = 1+0 = F_2$.  That is, $B$ is another re-indexed Fibonacci sequence, specifically, $B_k = F_{k-2}$.

Put together, this shows
$$F_{k+a-1} = F_{a+1}F_{k-1}+F_aF_{k-2}$$
which is exactly the identity we were looking for.  To make it look more alike, we can set $k=b+2$ to find
$$F_{a+b+1} = F_{a+1}F_{b+1}+F_aF_b$$
and changing $a$ to $a-1$ or $b$ to $b-1$ explicitly gives all the remaining identities.
