Another way to go about proving Binet's Formula

As I showed in another question of mine, it is easy to prove that

$$\tag{1}\phi^{n+1} =F_{n+1} \phi+F_{n }$$

given $F_1=1$ , $F_2=1$ , $F_{n+1}=F_n+F_{n-1}\text{ ; }n\geq2$.

Now, extending $(1)$ to negative and zero indices naturally yields: \eqalign{ & {F_{ 0}} = 0 \cr & {F_{ - 1}} = 1 \cr & {F_{ - 2}} = - 1 \cr & {F_{ - 3}} = 2 \cr & {F_{ - 4}} = - 3 \cr & {F_{ - n}} = {\left( { - 1} \right)^{n+1}}{F_{n}} \cr}

From this one has

$${\phi ^{ - n}} = {\left( { - 1} \right)^{n + 1}}\left( {{F_{n }}\phi - {F_{n + 1}}} \right)$$

A few examples:

\eqalign{ & {\phi ^{ - 1}} = \phi - 1 \cr & {\phi ^{ - 2}} = 2 - \phi \cr & {\phi ^{ - 3}} = 2\phi - 3 \cr}

Then one has that

\eqalign{ & {\left( { - \frac{1}{\phi }} \right)^n} = {F_{n + 1}} - {F_n}\phi \cr & {\phi ^n} = {F_n}\phi + {F_{n - 1}} \cr}

and consequently

\eqalign{ & {\phi ^n} + {\left( { - \frac{1}{\phi }} \right)^n} = {F_n}\phi + {F_{n - 1}} + {F_{n + 1}} - {F_n}\phi \cr & {\phi ^n} + {\left( { - \frac{1}{\phi }} \right)^n} = {F_{n + 1}} + {F_{n - 1}} \cr & {\phi ^n} + {\left( { - \frac{1}{\phi }} \right)^n} = {L_n} \cr}

How can this be put into an acceptable proof? (Note that given the relation between Lucas and Fibonacci numers, this straightforwardly gives Binet's Formula:

$${F_n} = \frac{1}{{\sqrt 5 }}\left[ {{\phi ^n} - {{\left( { - \frac{1}{\phi }} \right)}^n}} \right]$$

-
@AndréNicolas Fixed! –  Pedro Tamaroff Apr 18 '12 at 23:02
Does "from this one has" follow immediately? It does if the formula you started with (from earlier post) holds for negative $n$. (It has been a while since that post.) –  André Nicolas Apr 18 '12 at 23:19
@AndréNicolas The generalization is needed for the formula to hold. –  Pedro Tamaroff Apr 18 '12 at 23:20

Below is a proof of the uniqueness theorem for second order recurrences, which is employed in Will's answer. The proof generalizes to higher-order recurrences. It is a discrete analog of the better-known result for differential equations, using variation of parameters (see this answer, and see my my 2004/4/27 sci.math post for references).

Theorem $\$ If $\rm\:f,g,h\:$ are solutions of the recurrence

$$\rm \qquad\quad\ \ y''\: =\ p\ y' + q\ y,\ \ \ where\ \ \ y'(n)\, :=\, y(n\!+\!1)$$ with  Wronskian (Casoratian) $\rm\ \ W = g\:h'-g'h \ne 0\:$

then $\rm\,\exists\,\ \color{#c00}{ constants}\ \ c,d\,$ such that $\rm\: f = c\: g + d\: h,\ \ \rm\color{#c00}{i.e.\ \ c'=c,\ d' = d}$

Proof $\$ The equations $[0],[1]$ below have unique solution $\rm\:(c,d)\:$ via det $\rm = W \ne 0.$

$\rm[0]\qquad f\ =\ c\: g \: + d\: h$

$\rm[1]\qquad f' =\ c\: g' + d\: h'$

Now $\rm\:q\:[0] + p\:[1]\:$ yields:

$\rm[2]\qquad q\:f+p\:f'\: =\ f''\: =\ c\: g'' + d\: h''\$ via $\rm\ \ q\:g+p\:g'\: =\ g'',\ \ q\:h+p\:h'\: =\ h''$

$\rm[3]\qquad 0\ =\ (c'-c)\:g' \:+ (d'-d)\:h'\:\ \$ via $\ \ [0]'-[1]$

$\rm[4]\qquad 0\ =\ (c'-c)\:g'' + (d'-d)\:h''\ \$ via $\ \ [1]'-[2]$

$[3],[4]$ have solution $\rm\:(c'\!-c,d'\!-d) = (0,0),\:$ unique by $\rm\:det = W' = g'\:h''-g''\:h' \ne 0.\:$ Therefore $\rm\:c,d\:$ are constants, since $\rm\:c' = c\:$ means $\rm\:c(n+1) = c(n).\quad$ QED

Remark $\$ Note $\rm\, W = g\:h'-g'h = 0 \iff g/h =g'/h' = (g/h)'\iff g/h = c\,$ constant.

-

The set of sequences $x_n$ that have the property that $x_{n+2} = x_{n+1} + x_n,$ with, say, real number values, makes a vector space over the reals of dimension 2. Taking the two roots of $\lambda^2 = \lambda + 1,$ the larger being $$\phi = \frac{1 + \sqrt 5}{2}$$ and the smaller being $-1 / \phi,$ any such sequence, including index shifts, whatever you like, is a linear combination of two basis sequences, $$\ldots, 1/\phi, 1, \phi, \phi^2, \ldots$$ and $$\ldots, - \phi, 1, -1 / \phi, 1/ \phi^2, \ldots$$ where I am demanding that the element with value 1 have index 0 in both sequences. If I have any favorite sequence with $x_0, x_1$ specified, the equation to be solved for coefficients $A,B$ are $$A + B = x_0, \; \; \; A \phi - B / \phi = x_1.$$

So $$\left( \begin{array}{cc} 1 & 1 \\ \phi & -1/\phi \end{array} \right) \left( \begin{array}{c} A \\ B \end{array} \right) \; \; = \; \; \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right).$$ still composing...

$$\left( \begin{array}{c} A \\ B \end{array} \right) \; \; = \; \; \frac{-1}{\sqrt 5} \left( \begin{array}{cc} -1/\phi & -1 \\ -\phi & 1 \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right).$$ getting there...

Evidently you are taking $x_0 = 0, x_1 = 1,$ so we get $$\left( \begin{array}{c} A \\ B \end{array} \right) \; \; = \; \; \frac{-1}{\sqrt 5} \left( \begin{array}{cc} -1/\phi & -1 \\ -\phi & 1 \end{array} \right) \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \; \; = \; \; \left( \begin{array}{c} 1 / \sqrt 5 \\ -1/ \sqrt 5 \end{array} \right) .$$ My first basis sequence has elements labelled $y_n = \phi^n,$ and the second has $z_n = (-1/\phi)^n,$ so the Fibonacci sequence obeys $$x_n = \frac{1}{\sqrt 5} \; \; \phi^n \; \; \; - \; \; \; \frac{1}{\sqrt 5} \; \; \left( \frac{-1}{\phi} \right)^n.$$

-
And how does one prove that they are a linear combination of such sequences? What you're saying is that $$\left\langle {{\phi ^n},\frac{{{{\left( { - 1} \right)}^n}}}{{{\phi ^n}}}} \right\rangle$$ spans all the sequences of the form $${x_{n + 2}} = {x_{n + 1}} + {x_n}?$$ –  Pedro Tamaroff Apr 18 '12 at 23:45
@PeterT.off, yes. –  Will Jagy Apr 19 '12 at 0:10
can you provide a proof of that? I've seen this before, but as you can see, I choose other paths. –  Pedro Tamaroff Apr 19 '12 at 0:14
Such a sequence is completely determined once we know $x_0$ and $x_1$. Let $(a_n)$ and $(b_n)$ be the two sequences above. All you need to show is that we can find $u$ and $v$ such that $ua_0+vb_0=x_0$, $ua_1+vb_1=x_1$. Two linear equations in two unknowns. –  André Nicolas Apr 19 '12 at 0:16
@PeterT.off, I think I would add that the fact that such a sequence is completely determined once $x_0, x_1$ are known is an exercise in mathematical induction: if two sequences $x,y$ agree for indices from $0$ to $n,$ show that they agree at index $n+1.$ Next, if they agree for indices $1$ down to $-n,$ show that they agree at index $-n-1.$ That shows the dimension of the vector space is 2. Another basis is the Fibonacci and Lucas sequences. –  Will Jagy Apr 19 '12 at 0:25
show 3 more comments

I might as well point out how to use your way. We have the following two equations:

$$\varphi^{n+1}=F_{n+1}\varphi+F_{n} \tag{1}$$ $$(-1/\varphi)^n=F_{n+1}-F_n\varphi \tag{2}$$

For $(1)$, decrease $n$ by $1$, and for $(2)$ do the same but then divide both sides by $\varphi$. We obtain

$$\varphi^n=F_n\varphi+F_{n-1} \tag{a}$$ $$-(-1/\varphi)^n=F_n/\varphi-F_{n-1} \tag{b}$$

Now add $\rm(a)$ and $\rm(b)$ together and divide by $\varphi+1/\varphi=\sqrt{5}$ to obtain Binet's. This is analogous to what you did for Lucas numbers.

-
@PeterT.off I'm not sure I understand your question then. What's unacceptable about your current proof of Binet's, besides the fact you weren't explicit about the "straightforward" part at the end? –  anon Apr 19 '12 at 1:20