4
$\begingroup$

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]$

  • 0
    @AndréNicolas The generalization is needed for the formula to hold.2012-04-18

3 Answers 3

3

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.

2

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

  • 0
    Tha$n$ks for the explanations, @Will. I will try to make the most out of it.2012-04-19
1

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.

  • 0
    @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?2012-04-19