The Fibonacci numbers $F_n$ and Lucas numbers $L_n$ both satisfy the recurrence relation $x_n=x_{n-1}+x_{n-2}$. The Fibonacci numbers start $0,1$ while the Lucas numbers start $2,1$. I would like to know about the theory underpinning them, in particular, the analogies with differential equations ($\sin$ and $\cos$) and how it works for for higher order (linear, homogeneous, constant-coefficient) difference equations.

I have many questions

  • Are the two sequences linearly independent? Orthogonal?

  • Given $F_0=0$ and $F_1=1$ does this define $L_n$? How?

  • $\sin$ and $\cos$ have $0,1$ and $1,0$ as $f(0)$ and $f'(0)$, respectively. Can we view $F_n$ and $L_n$ similarly?

On the page: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/lucasNbs.html they say that (2,1) is chosen because they are the two "simplest" (positive) numbers which don't produce the Fibonacci numbers (or shifted versions of them). Also, they seem to exclude (0,2) which produces the Fibonacci numbers.

(I need to to read the following page http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibGen.html#gstart to work out what "simplest" really means and why the choice (0,1) and (2,1) give rise to so many nice properties.)


You have already answered your own question, essentially. The space $E$ of sequences $\{a_n\}_{n\geq 0}$ fulfilling $a_{n+2}=a_{n+1}+a_n$ is a vector space with dimension $2$; any sequence belonging to $E$ is fixed by its initial values $a_0$ and $a_1$. The initial values of the Fibonacci sequence are $0,1$; the initial values of the Lucas sequence are $2,1$; since $(0,1)$ and $(2,1)$ are linearly independent each sequence in $E$ can be represented through $a_n = f\cdot F_n + l\cdot L_n$ for some constants $f,l$. For instance, this applies to the shifted Fibonacci and Lucas sequences: $$ L_{n+1} = \frac{5}{2}F_n+\frac{1}{2}L_n,\qquad F_{n+1}=\frac{1}{2}F_n+\frac{1}{2}L_n $$ and you may also take $\{F_n\}_{n\geq 0},\{F_{n+1}\}_{n\geq 0}$ or $\{L_n\}_{n\geq 0},\{L_{n+1}\}_{n\geq 0}$ as a base for $E$.
The canonical choice should have been $(1,0),(0,1)$ associated to $\{F_{n-1}\}_{n\geq 0},\{F_{n}\}_{n\geq 0}$, but there are arithmetic reasons for picking $\{F_n\}_{n\geq 0}$ and $\{L_n\}_{n\geq 0}$ as the "mostly peculiar" elements of $E$ (see the comments below).

A sequence with a moderate growth can be associated to an analytic function via $$ \{a_n\}_{n\geq 0}\quad \mapsto\quad g(x)=\sum_{n\geq 0}a_n x^n $$ (the RHS is known as the ordinary generating function (OGF) of the sequence) and this gives a tight relation between linear recurrent sequences, linear differential equations and the elements of $M^n$ with $M$ being a fixed matrix. You guessed it correctly: they all appear to be the same problem because they actually are the same problem.

Here it is a brief outline of the power of the previous association $\text{sequence}\mapsto\text{OGF}$, relying on the fact that we may go in the opposite direction by Cauchy's integral formula or something equivalent to it. Since in the Fibonacci sequence each term with $n\geq 2$ is given by the sum of the previous two terms, when we multiply the $\text{OGF}$ by $1-x-x^2$ there has to occur a massive cancellation, leaving out at most two monomials. Indeed, by interpolation: $$ \sum_{n\geq 0}F_n x^n = \frac{x}{1-x-x^2}.$$ This is beautiful, since we may factor the polynomial $1-x-x^2$, apply a partial fraction decomposition to the RHS and recall that $$ \frac{1}{1-\alpha x} = \sum_{n\geq 0} \alpha^n x^n $$ holds for any $\alpha$ such that $|\alpha|<1$. By the unicity of the Maclaurin series of the $\text{OGF}$, the explicit formula $$ F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right] $$ is proved. We may apply the same technique to the sequence of Lucas numbers: the only different step is the interpolation step, leading to $$ L_n = \left[\left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n\right]=\text{Tr}\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n. $$ If we replace the constants $\varphi,1-\varphi$ with the constants $e^i, e^{-i}$ we have that $F_n$ is "essentially a (hyperbolic) sine" and $L_n$ is "essentially a (hyperbolic) cosine". Rigorously, $$\boxed{ F_n = \frac{2}{\sqrt{5}}\,\sinh(n\log\varphi),\qquad L_n = 2\cosh(n\log\varphi)\,}$$ and this also allows to define $F_n$ or $L_n$ for non-integer values of $n$.

  • $\begingroup$ Yes, but why not take (0,1) (Fibonacci) and (1,0)? Or (1,1) and (0,1)? $\endgroup$ – pdmclean Apr 3 '18 at 5:33
  • $\begingroup$ @pdmclean: I believe that the reason for the choice $(0,1),(2,1)$ relies on the fact that the Fibonacci sequence has the nice divisibility property $F_n\mid F_{nm}$ while the Lucas sequence is given by a sequence of traces of $M^n$. $\endgroup$ – Jack D'Aurizio Apr 3 '18 at 5:37
  • $\begingroup$ Perhaps related: the Fibonacci and Lucas numbers form a oeis.org/wiki/Autosequence pair or en.wikipedia.org/wiki/Lucas_sequence pair. $\endgroup$ – pdmclean Apr 3 '18 at 5:39
  • $\begingroup$ @pdmclean: true, but that is just a consequence of the fact that the roots of the characteristic polynomial $x^2-x-1$ comes in a pair $\alpha,1-\alpha$ by Vieta's formula. That holds for each element of $E$. $\endgroup$ – Jack D'Aurizio Apr 3 '18 at 5:43
  • $\begingroup$ We also have $F_{2n}= F_n L_n$ resembling the sine duplication formula with a dropped factor $2$. This is a straightforward consequence of the explicit formulas: just like $F_n$ is similar to $\sin(n)=\frac{e^{in}-e^{-in}}{2i}$, $L_n$ is similar to $\cos(n)=\frac{e^{in}+e^{-in}}{2}$. $\endgroup$ – Jack D'Aurizio Apr 3 '18 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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