Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
1  
@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.

share|improve this answer
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.