# Binet's Formula. An operational approach.

I read quite a while ago this proof of Binet's formula. ( I am not 100% sure this is the way it was presented, but it gives an idea. I'm not approving of this method or saying it is correct.)

Let $\hat{S}$ be an operator such that

$$\hat{S}a_n =a_{n+1}$$

Then, we can define Fibonacci's numbers this way

$$\hat{S}^2a_n =\hat{S}a_n+a_n$$

Solving for $\hat{S}$ gives

$$\left(\hat{S}^2-\hat{S}-1\right)a_n=0$$

Since $a_n\neq 0$ for all Fibonacci numbers, we necesarrily need:

$$\hat{S}^2-\hat{S}-1=0$$

This gives

$$\hat{S} = \frac{1\pm\sqrt{5}}{2}$$

But $$\hat{S}^n a_1 = a_n$$ and $a_1 = 1$.

Then they explain that since $\hat{S} = \dfrac{1\pm\sqrt{5}}{2}$ "it is natural to expect $a_n$ to be a linear combination of the $n$-th powers of $\phi$ and $1-\phi$", i.e.

$$a_n = A\phi^n+B(1-\phi)^n$$

Now we simply find $A$ and $B$ by equating to some know values, and get

$$a_n = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}}$$ which is Binet's formula.

Could you explain what are the formal basis for this type of proofs/solutions to this problems and what is the motivation for the last supposition?

-
@AndréNicolas That's not the idea of the proof. The proof clearly uses the fact that $1-\phi = \dfrac{1-\sqrt{5}}{2}$ is the other root. –  Pedro Tamaroff Feb 15 '12 at 22:12
If that is made explicit, fine. One still does not expect $a_n$ to be a linear combination of the roots, but of the $n$-th powers of the roots. My preferred way of putting it is that if $\alpha$ and $\beta$ are the roots, then $\alpha^n$ and $\beta^n$ both satisfy the recurrence, and therefore by linearity so does any linear combination. And one can express the hope (which is correct if the roots are distinct) that any solution is a linear combination. Same process as solving a second-order homogeneous DE with constant coefficients. –  André Nicolas Feb 15 '12 at 22:25
I don't think I understand what's going on here. Just because an operator (here $\hat{S}^2-\hat{S}-1$) annihilates a particular sequence (here the Fibonacci numbers) doesn't mean it is the zero operator. –  anon Feb 15 '12 at 22:25
@AndréNicolas Ok. I'll correct that, since I did write it as a LC of the $n$-th powers but didn't write it correctly. –  Pedro Tamaroff Feb 15 '12 at 22:27
This is a very, very poor presentation. To begin it makes the error all my students make of writing the shift operator $S$, which acts on infinite sequences (by chopping off the first term) as if it operates on the individual terms $a_i$ of the sequence. It does not. It doesn't modify any number, it just makes the terms change places in the sequence. The first formula should read $S((a_n)_{n\in\mathbf N})=(a_{n+1})_{n\in\mathbf N}$. The formula $S^n(a_1)=a_n$ is even worse, there is no way to make sense of that one at all. You need to understand these points for the argument. –  Marc van Leeuwen Feb 15 '12 at 22:38

Frankly, I think that it’s a very poor presentation. If $\hat S$ is an operator that transforms $a_n$ to $a_{n+1}$, it is not a real number, though it might conceivably be a function that operates by multiplying by a specific real number. A more honest presentation of the same basic idea would go something like this.

If we examine the Fibonacci sequence empirically, we quickly discover that it grows approximately exponentially: it takes very little calculation to see that $a_{n+1}/a_n$ seems to be converging to some number a little larger than $1.6$. We might then ask whether there are any purely exponential sequences that satisfy the Fibonacci recurrence. The calculations in the argument that you presented show that there are two, one with ratio $\varphi=\frac12(1+\sqrt5)$ and one with ratio $\hat\varphi=\frac12(1-\sqrt5)=1-\varphi$. That is, for any $n\ge 2$ we have $$\varphi^n=\varphi^{n-1}+\varphi^{n-2}\tag{1}$$ and $$\hat\varphi^n=\hat\varphi^{n-1}+\hat\varphi^{n-2}\tag{2}\;,$$ and $\varphi$ and $\hat\varphi$ are the only two non-zero real numbers with this property.

Clearly any linear combination of $(1)$ and $(2)$ also holds: for any real numbers $\alpha$ and $\beta$, $$\alpha\varphi^n+\beta\hat\varphi^n=(\alpha\varphi^{n-1}+\beta\hat\varphi^{n-1})+(\alpha\varphi^{n-2}+\beta\hat\varphi^{n-2})\;.$$ Thus, any sequence defined by $$a_n=\alpha\varphi^n+\beta\hat\varphi^n\tag{3}$$ for some $\alpha,\beta\in\mathbb{R}$ must satisfy the Fibonacci recurrence. In fact it turns out that these are also the only sequences that satisfy it, but we don’t need to know this in order to ask whether the Fibonacci sequence has the form $(3)$; and as you say, this is easily determined by substituting some known values and solving for $\alpha$ and $\beta$. In fact, this is one way to show that $(3)$ generates all sequences satisfying the Fibonacci recurrence: merely note that once $a_0$ and $a_1$ are known, $(3)$ yields the system $$\begin{cases}a_0=\alpha+\beta\\a_1=\alpha\varphi+\beta\hat\varphi\end{cases}\;,$$ which is easily shown to have a unique solution.

There are more sophisticated ways to arrive at the same result more directly. For example, one might notice that the Fibonacci recurrence implies that $$\pmatrix{F_{n+1}\\F_n}=\pmatrix{1&1\\1&0}\pmatrix{F_n\\F_{n-1}}\;,$$ so $$\pmatrix{F_{n+1}\\F_n}=\pmatrix{1&1\\1&0}^n\pmatrix{1\\0}\;.$$ This allows $F_n$ to be expressed fairly easily in terms of the eigenvalues of $\pmatrix{1&1\\1&0}$, which turn out to be $\varphi$ and $\hat\varphi$. However, I think that the argument that I outlined above is a fair representation of the reasoning underlying the argument that you gave.

-
Thank you very much. –  Pedro Tamaroff Feb 15 '12 at 22:24

Hint: the key is to factor $S^2 - S - 1 = (S-\phi)(S-\phi')$. Because $S-\phi,\ S-\phi'$ commute, both solutions $\phi^n,\ \phi'^n$ of $(S-\phi) a_n = 0 = (S-\phi') a_n$ yield solutions of $(S-\phi)(S-\phi')\:a_n = 0$. Hence by linearity the latter has solutions $a_n = c_1\: \phi^n + c_2\: \phi'^n$ for "constants" $c,\:$ i.e. $\:S c\: =\: c$.

That these are the only solutions follows from general principles about the dimension of the vector space of solutions, analogous to that for ODEs, using variation of parameters and discrete analogs of Wronskians (Casoratians), e.g. see here.

-
Thank you for the link. –  Pedro Tamaroff Feb 15 '12 at 22:30