3
$\begingroup$

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?

  • 0
    @MarcvanLeeuwen This is by no means my production. It's just something I read a long time ago and was very baffled by. Thanks for explaining that. I guess the solution is kind of "umbral".2012-02-15

2 Answers 2

2

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.

2

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.