(I'm assuming here that what the OP really wants is to know how one would ever get the idea to try to prove this. He already has a proof by induction, which is a perfectly valid and respectable proof method; you won't get anything proofier than that, except perhaps methods that hide the induction within a general theorem).
One way to invent this relation is to start from the following fairly simple algorithm for computing Fibonacci numbers:
- Start by setting $a=0$, $b=1$
- Repeat the following until you reach the $F_n$ you want:
- (Invariant: $a=F_{n-1}$ and $b=F_n$).
- Set $c=a+b$
- (Now $c=F_{n+1}$)
- $a\leftarrow b$ and $b \leftarrow c$.
Now observe that the loop body computes the new $a$ and $b$ as linear combinations of the old $a$ and $b$. Therefore there's a matrix that represents each turn through the loop. Many turns through the loop become multiplication with a power of the matrix.
This reasoning gives you the matrix $M=\pmatrix{1&1\\1&0}$ and an informal argument that $M^n \pmatrix{1\\0} = \pmatrix{F_n\\F_ {n-1}}$. This gives us one column of $M^n$, and it is reasonable to hope that the other one will also be something about Fibonacci numbers. One can either repeat the previous argument with different starting $a$ and $b$, or simply compute the first few powers of $M$ by hand and then recognize the pattern to be proved formally later.