14
$\begingroup$

$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$

Somebody has any idea how to go about proving this result? I know a proof by mathematical induction, but that, in my opinion, will be a verification of this result only. I tried to find through the net, but in vain, if someone has some link or pointer to its proof, please provide, I'll appreciate that.

Thanks a lot!

  • 0
    See also: http://math.stackexchange.com/questions/693905/proof-by-mathematical-induction-fibonnaci-numbes-and-matrices2015-11-07

3 Answers 3

5

(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.

  • 0
    @Ste Indeed, it may prove useful to mention both general and special answers. Furthermore, it is helpful to *explicitly* point out the relationship between the general and special answers, since that may not obvious to the reader.2011-09-05
5

Set $u_n = (F_{n+1} , F_{n} )^T$. Then $u_{n+1} = A u_n$, where $ A = \begin{pmatrix}1&1\\1&0\end{pmatrix} $ and so $ u_{n} = A^n \ u_0 $. Since $u_0 = (1 ,0)^T$, the first column of $A^n$ is $u_n$. If you define $F_{-1}=1$, then the second column of $A^n$ is $A^n (0,1)^T = A^n u_{-1} = A^{n-1}u_0$, and so is the first column of $A^{n-1}$, which is $u_{n-1}$, as we have seen.

  • 1
    @RFZ, it makes the recurrence work. It's not uncommon. See https://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers.2017-11-28
5

HINT $\ $ The same works for any sequence $\rm\:\:f_i\:$ satisfying a constant coefficient linear $\rm\:k$'th order recurrence. Namely the shift map $\rm\: S\: (f_k,\:\ldots,f_2,f_1)\: =\: (f_{k+1},\ldots,f_3,f_2)\:$ has matrix being a constant coefficient companion matrix. So $\rm\:S^n,\:$ a shift by $\rm\:n,\:$ has matrix an $\rm\:n$'th power of said companion matrix. If the recurrence had nonconstant coefficients, i.e. coefficients depending on the index $\rm\:k\:,\:$ then said shift $\rm\:S^n$ would not be an $\rm\:n$'th power of a constant coefficient matrix but, rather, a product of $\rm\:n\:$ matrices with variable coefficients (i.e. depending on the index $\rm\:k\:)\:.$

Note that this matrix representation yields addition formulas and fast polynomial-time algorithms for computing the sequence by computing matrix powers by repeated squaring.