Fibonacci series

Hyperbolic sine representation of mth Fibonacci number

July 26, 2024 math and physics play , , , , ,

[Click here for a PDF version of this post]

I saw a funky looking formula for the mth Fibonacci number on twitter
\begin{equation}\label{eqn:fibonacci_sinh:20}
F_m = \frac{2}{\sqrt{5} i^m} \sinh\lr{ m \ln\lr{i\phi} },
\end{equation}
where
\begin{equation}\label{eqn:fibonacci_sinh:60}
\phi = \frac{ 1 + \sqrt{5} }{2},
\end{equation}
is the golden ratio.

This certainly doesn’t look like it’s a representation of the sequence
\begin{equation}\label{eqn:fibonacci_sinh:40}
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \cdots
\end{equation}
We can verify that it works in Mathematica, as seen in fig. 1.

fig. 1. Verification of hyperbolic sine representation of mth Fibonacci numbe

Recall that we previously found this formula for the mth Fibonacci number
\begin{equation}\label{eqn:fibonacci_sinh:80}
F_m = \inv{\sqrt{5}} \lr{ \phi^m – { \bar{\phi}}^m },
\end{equation}
where \( \bar{\phi} \) is the conjugate of the golden ratio
\begin{equation}\label{eqn:fibonacci_sinh:100}
\bar{\phi} = \frac{ 1 – \sqrt{5} }{2}.
\end{equation}

Let’s see how these are equivalent. First observe that the golden conjugate is easily related to the inverse of the golden ratio
\begin{equation}\label{eqn:fibonacci_sinh:120}
\begin{aligned}
\inv{\phi}
&=
\frac{2}{1 + \sqrt{5}} \\
&=
\frac{2\lr{ 1 – \sqrt{5}} }{1^2 – \lr{\sqrt{5}}^2 } \\
&=
-\frac{1 – \sqrt{5} }{2} \\
&=
-\bar{\phi}.
\end{aligned}
\end{equation}
Substitution gives
\begin{equation}\label{eqn:fibonacci_sinh:140}
F_m = \inv{\sqrt{5}} \lr{ \phi^m – \lr{\frac{-1}{\phi}}^m }.
\end{equation}
Multiplying by \( i^m \), we have
\begin{equation}\label{eqn:fibonacci_sinh:160}
\begin{aligned}
i^m F_m
&= \inv{\sqrt{5}} \lr{ i^m \phi^m – \inv{(-i)^m} \lr{\frac{-1}{\phi}}^m } \\
&= \inv{\sqrt{5}} \lr{ \lr{ i \phi} ^m – \lr{i \phi}^{-m} } \\
\end{aligned}
\end{equation}

We can write any exponent in terms of \( e \)
\begin{equation}\label{eqn:fibonacci_sinh:180}
a^m = e^{\ln a^m} = e^{m \ln a},
\end{equation}
so
\begin{equation}\label{eqn:fibonacci_sinh:200}
\begin{aligned}
i^m F_m
&= \inv{\sqrt{5}} \lr{ e^{m \ln \lr{ i \phi}} – e^{-m \ln\lr{i \phi} } } \\
&= \inv{\sqrt{5}} 2 \sinh\lr{ m \ln \lr{ i \phi } },
\end{aligned}
\end{equation}
as we wanted to show. It’s a bit strange looking, but we see why it works.

Deriving the nth Fibonacci number formula.

November 20, 2020 math and physics play , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

My last three posts:

  1. The nth term of a Fibonacci series.
  2. More on that cool Fibonacci formula.
  3. Guessing the nth Fibonacci number formula.

were all about a cool formula for the n-th term of the Fibonacci series.  Here’s the final chapter of the story of that play.  A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

Deriving the nth Fibonacci formula.

There was a particularly unsatisfactory aspect of the guess that we made in the last post. In particular, we didn’t have any reason to guess the form of that solution, except for the fact that we already knew the answer. Now we will attempt to attack this in a more systematic fashion, so that each step along the way seems logical. First, we need to put a couple goodies in our toolbox.

Definition 1.1: Discrete sum.

Given a set of discrete values \( \setlr{G_a, G_{a+1}, \cdots, G_n } \) we define a discrete sum of \( n – a + 1 \) of these terms as \( F_n \)
\begin{equation}\label{eqn:fibonacciblog:1540}
F_n = \sum_{k = a}^n G_k + C,
\end{equation}
where \( C \) is an arbitrary boundary value constant.

Definition 1.2: Difference operators.

Define a backwards difference operator \( \Delta \), operating on \( X_n \) as
\begin{equation}\label{eqn:fibonacciblog:1560}
\Delta X_n = X_n – X_{n-1}.
\end{equation}

The difference operator is a discrete analogue of a differential operator. It is also possible to define a (forward) difference operator as \( \Delta X_n = X_{n+1} – X_{n} \), but the choice is arbitary, and we can find the same results either way.

Lemma 1.1: Antidifference of discrete sum.

Given a sum \( F_n \) of the form \ref{eqn:fibonacciblog:1540}, the difference operation is just the highest \( n \) term of the sum
\begin{equation}\label{eqn:fibonacciblog:1580}
\Delta F_n = G_n.
\end{equation}

Start proof:

\begin{equation}\label{eqn:fibonacci:960}
\Delta F_n =
\sum_{k = a}^n G_k + C
– \lr{ \sum_{k = a}^{n-1} G_k + C }
= G_n.
\end{equation}

End proof.

Computing differences is pretty easy. What we want to do is the inverse operation (analogous to integration), where we find a closed form representation of \( F_n \) given a difference equation \( \Delta F_n = G_n \). Just as we can compute antiderivatives for \( x^n \), we may do the same for \( n^k \) antidifferences, but the results are messier. The first few such antidifferences are

Theorem 1.1: Antidifferences for powers of \(n\).

\begin{equation}\label{eqn:fibonacciblog:1600}
\begin{aligned}
1 &= \Delta n \\
n &= \Delta \lr{ \frac{n}{2}\lr{ n + 1} } \\
n^2 &= \Delta \lr{ \frac{n}{6}\lr{2 n + 1}\lr{n + 1} } \\
n^3 &= \Delta \lr{ \frac{n^2}{4}\lr{n + 1}^2 }.
\end{aligned}
\end{equation}

Start proof:

The \( \Delta n \) identity is easily verified
\begin{equation}\label{eqn:fibonacci:1000}
\Delta n = n – (n-1) = 1.
\end{equation}
For higher orders it is a bit tedious to verify directly, but we can iteratively build up those results by evaluating the difference operator on each of the powers of \( n \).
\begin{equation}\label{eqn:fibonacci:660}
\begin{aligned}
\Delta n^2
&= n^2 – (n-1)^2 \\
&= n^2 – (n^2 – 2 n + 1) \\
&= 2 n – 1, \\
&= 2 n – \Delta n.
\end{aligned}
\end{equation}
Because the difference operator is linear, we can rearrange to find
\begin{equation}\label{eqn:fibonacci:1020}
\Delta \lr{ n^2 + n } = 2 n.
\end{equation}
Dividing through by \( 2 \) and factoring out an \( n \), recovers the desired result.

For the next power, we have
\begin{equation}\label{eqn:fibonacci:680}
\begin{aligned}
\Delta n^3
&= n^3 – (n-1)^3 \\
&= n^3 – (n^3 – 3 n^2 + 3 n – 1) \\
&= 3 n^2 – 3 n + 1 \\
&= 3 n^2 – 3 \Delta \frac{n}{2}\lr{ n + 1 } + \Delta n,
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:1040}
\begin{aligned}
3 n^2
&=
\Delta \lr{n} \lr{ n^2 + \frac{3}{2}\lr{ n + 1} – 1 } \\
&=
\Delta \frac{n}{2} \lr{ 2 n^2 + 3\lr{ n + 1} – 2} \\
&=
\Delta \frac{n}{2} \lr{ 2 n^2 + 3 n + 1 } \\
&=
\Delta \frac{n}{2} \lr{ 2 n + 1}\lr{ n + 1 }
\end{aligned}
\end{equation}
Dividing through by \( 3 \) recovers the desired result.

The final result is left to the reader. It can be derived or verified easily with a couple lines of Mathematica code.

End proof.

Problem: Sum some series.

Find the sums \( \sum_{k = 1}^n k^m \), for \( m = 1, 2, 3 \).

Answer

  • \( m = 1 \). This is the (probably apocryphal) sum of Gauss’s grade school classroom:
    \begin{equation}\label{eqn:fibonacci:1060}
    F_n = \sum_{k = 1}^n k = 1 + 2 + \cdots n,
    \end{equation}
    satisfying
    \begin{equation}\label{eqn:fibonacci:1080}
    \begin{aligned}
    \Delta F_n
    &= F_n – F_{n-1} \\
    &=
    (n + (n-1) + \cdots + 1)
    –
    ((n-1) + \cdots + 1) \\
    &= n \\
    &= \Delta \frac{n}{2}(n + 1).
    \end{aligned}
    \end{equation}
    We must have
    \begin{equation}\label{eqn:fibonacci:1100}
    F_n = \frac{n}{2}\lr{ n + 1} + C.
    \end{equation}
    To fix \( C \) consider \( F_1 \)
    \begin{equation}\label{eqn:fibonacci:1180}
    F_1 = \inv{2}(1 + 1) + C = 1,
    \end{equation}
    so \( C = 0 \), so we find Gauss’s summation formula
    \begin{equation}\label{eqn:fibonacci:1200}
    \sum_{k = 1}^n k = \frac{n}{2}\lr{ n + 1},
    \end{equation}
    as expected.
  • \( m = 2 \). Now let’s do the sum of squares
    \begin{equation}\label{eqn:fibonacci:1120}
    F_n = \sum_{k = 1}^n k^2,
    \end{equation}
    for which we have
    \begin{equation}\label{eqn:fibonacci:1140}
    \Delta F_n = n^2 = \Delta \frac{n}{6}( 2 n + 1 )(n+1),
    \end{equation}
    so
    \begin{equation}\label{eqn:fibonacci:1160}
    F_n = \frac{n}{6}( 2 n + 1 )(n+1) + C.
    \end{equation}
    Clearly \( C = 0 \) satisfies the boundary condition, leaving
    \begin{equation}\label{eqn:fibonacci:1220}
    \sum_{k = 1}^n k^2 =
    \frac{n}{6}( 2 n + 1 )(n+1).
    \end{equation}
  • \( m = 3 \). We see the pattern, so for the sum of cubes, we can just write down the answer
    \begin{equation}\label{eqn:fibonacci:1240}
    \sum_{k = 1}^n k^3 =
    \frac{n^2}{4}\lr{n + 1}^2
    .
    \end{equation}

Now that we have some basic comfort with the ideas of difference equations, and their solutions,
let’s get back to the Fibonacci problem. In that case, we have
\begin{equation}\label{eqn:fibonacci:1260}
F_n = F_{n-1} + F_{n-2}.
\end{equation}
Stated as a difference equation, this is
\begin{equation}\label{eqn:fibonacci:1280}
\Delta F_n = F_{n-2}.
\end{equation}
Before tackling the Fibonacci problem, let’s try one that slightly simpler.

Problem: A simpler problem.

Solve \( \Delta F_n = F_{n-1} \), where \( F_0 = 0, F_1 = 1 \).

Answer

The problem to solve is just
\begin{equation}\label{eqn:fibonacci:1300}
F_n = 2 F_{n-1}.
\end{equation}
This sequence is \( \setlr{ 1, 2, 4, 8, \cdots } \), so we can solve it by inspection, and the answer is just \( F_n = 2^{n-1} \). We want inspiration for the Fibonacci problem, so let’s pretend that we can’t see the answer, but that we can guess something close, and see if it works. Namely, let’s guess:
\begin{equation}\label{eqn:fibonacci:1320}
F_n = \alpha a^n + C.
\end{equation}
If we plug this trial solution into our difference equation, we get
\begin{equation}\label{eqn:fibonacci:1340}
\begin{aligned}
\alpha a^{n-1} + C
&=
\Delta F_n \\
&= \alpha \lr{ a^n – a^{n-1} } \\
&= \alpha a^{n-1} \lr{ a – 1 }
\end{aligned}
\end{equation}
This can be satisfied by setting \( C = 0 \) and \( a – 1 = 1 \), or \( a = 2 \), as we already knew. To fix the constant \( \alpha \) we utilize our boundary constraints, namely
\begin{equation}\label{eqn:fibonacci:1400}
F_1 = 1 = \alpha 2
\end{equation}
so \(\alpha = 1/2 \).

Compared to just seeing the answer, the procedure above was a lot of work. However, a side effect of this work is discovery of a guessing strategy that is somewhat like using \( f(t) = e^{s t} \) to generate a characteristic equation when solving a differential equation. For a difference equation of this form, it appears we can substitute \( F_n = \alpha a^n + C \) and use the differences to determine the values of \( \alpha, a, C \). Now let’s try this with the Fibonacci difference equation.

Problem: Find a solution to the Fibonacci difference equation.

Without worrying about boundary constraints, find the solutions to \( \Delta F_n = F_{n-2} \), using a trial solution of \( F_n = \alpha a^n \).

Answer

Inserting our trial solution, we have
\begin{equation}\label{eqn:fibonacci:1420}
\begin{aligned}
\alpha a^n
&=
F_n \\
&= F_{n-1} + F_{n-2} \\
&= \alpha \lr{ a^{n-1} + a^{n-2} } \\
&= \alpha a^{n-2} \lr{ a + 1 },
\end{aligned}
\end{equation}
so our “characteristic equation” is
\begin{equation}\label{eqn:fibonacci:1440}
a + 1 = a^2.
\end{equation}
Completing the square yields
\begin{equation}\label{eqn:fibonacci:1460}
\lr{ a – \inv{2} }^2 = 1 + \inv{4},
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:1480}
a = \inv{2} \pm \frac{\sqrt{5}}{2}.
\end{equation}
Bamn. There’s our golden ratio, and it’s buddy!
We find that
\begin{equation}\label{eqn:fibonacci:1500}
F_n = \alpha \lr{\frac{1 \pm \sqrt{5}}{2} }^n,
\end{equation}
are solutions to the difference equation \ref{eqn:fibonacci:1280}.

Since we have a second order difference equation, we need a superposition of both solutions to try to satisfy the boundary conditions. In particular, we want to find the constants
\begin{equation}\label{eqn:fibonacci:1520}
F_n =
\alpha_{+} \lr{\frac{1 + \sqrt{5}}{2} }^n
+
\alpha_{-} \lr{\frac{1 – \sqrt{5}}{2} }^n + C.
\end{equation}
However, we already did this when we guessed used \( F_n = \alpha a^n + \beta b^n \) as a trial solution. When we did that, it was just to see if we could find the end result, knowing only the structure of the solution, but none of the specific constants. Now we have justified why that was a reasonable trial solution, since exactly this structure follows naturally from the difference equation itself.

This train of thought, makes me want to dig out my little Dover book on difference equations [1] that I’ve had since I was a kid. I think I only worked through the first chapter of that book. I have a lot of little sad neglected Dover books on mathematics and physics that I bought super cheap at the World’s Biggest Bookstore when I was back in school. It will be interesting to see how to tackle problems such as this, in a still more systematic fashion.

References

[1] Hyman Levy and Freda Lessman. Finite difference equations. Courier Corporation, 1992.

Guessing the nth Fibonacci number formula

November 17, 2020 math and physics play , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

My last two posts:

  1. The nth term of a Fibonacci series.
  2. More on that cool Fibonacci formula.

were both about a cool formula for the n-th term of the Fibonacci series.  Looks like I’m not done playing with this beastie.  A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

 

The guess.

We can rearrange the formula for the nth Fibonacci number as a difference equation
\begin{equation}\label{eqn:fibonacci:260}
F_n – F_{n-1} = F_{n-2}.
\end{equation}
This is a second order difference equation, so my naive expectation is that there are two particular solutions involved. We know the answer, so it’s not too hard to guess that the particular form of the solution has the following form
\begin{equation}\label{eqn:fibonacci:280}
F_n = \alpha a^n + \beta b^n.
\end{equation}
Given this guess, can we take some of the magic out of the formula, by just solving for \( \alpha, \beta, a, b \)? Let’s try that
\begin{equation}\label{eqn:fibonacci:300}
F_0 = \alpha + \beta = 0,
\end{equation}
\begin{equation}\label{eqn:fibonacci:320}
\begin{aligned}
F_1 &= \alpha a + \beta b \\
&= \alpha \lr{ a – b } \\
&= 1,
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:fibonacci:340}
\begin{aligned}
F_n
&= F_{n-1} + F_{n-2} \\
&=
\alpha \lr{ a^{n-1} + a^{n-2} }
-\alpha \lr{ b^{n-1} + b^{n-2} } \\
&=
\alpha a^{n-2} \lr{ 1 + a }
-\alpha b^{n-2} \lr{ 1 + b },
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:360}
\begin{aligned}
a^2 &= a + 1 \\
b^2 &= b + 1.
\end{aligned}
\end{equation}
If we complete the square we find
\begin{equation}\label{eqn:fibonacci:380}
\lr{ a – \inv{2} }^2 = 1 + \inv{4} = \frac{5}{4},
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:400}
a, b = \inv{2} \pm \frac{\sqrt{5}}{2}.
\end{equation}
Out pop the golden ratio and it’s complement. Clearly we need to pick alternate roots for \( a \) and \( b \) or else we’d have zero for every value of \( n > 0 \). Suppose we pick the positive root for \( a \), then to find the scaling constant \( \alpha \), we just compute
\begin{equation}\label{eqn:fibonacci:420}
\begin{aligned}
1
&=
\alpha \lr{ \frac{ 1 + \sqrt{5}}{2} – \frac{ 1 – \sqrt{5} }{2} } \\
&= \alpha \sqrt{5},
\end{aligned}
\end{equation}
so our system \ref{eqn:fibonacci:280} has the solution:
\begin{equation}\label{eqn:fibonacci:520}
\begin{aligned}
a &= \frac{1 + \sqrt{5}}{2} \\
b &= \frac{1 – \sqrt{5}}{2} \\
\alpha &= \inv{\sqrt{5}} \\
\beta &= -\inv{\sqrt{5}}.
\end{aligned}
\end{equation}

We now see a path that will systematically lead us from the Fibonacci difference equation to the final result, and have only to fill in a few missing steps to understand how this could be discovered from scratch.

Motivating the root-fives.

I showed this to Sofia, and she came up with a neat very direct way to motivate the \( \sqrt{5} \). It follows naturally (again knowing the answer), by assuming the Fibonacci formula has the following form:
\begin{equation}\label{eqn:fibonacci:440}
F_n = \inv{x} \lr{
\lr{ \frac{1 + x}{2}}^n
–
\lr{ \frac{1 – x}{2}}^n
}.
\end{equation}
We have only to plug in \( n = 3 \) to find
\begin{equation}\label{eqn:fibonacci:460}
\begin{aligned}
2 x
&= \inv{4} \lr{ 1 + 3 x + 3 x^2 + x^3 – \lr{ 1 – 3 x + 3 x^2 – x^3 } } \\
&= \inv{2} \lr{ 3 x + x^3 },
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:480}
8 = 3 + x^2,
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:500}
x = \pm \sqrt{5}.
\end{equation}
Again the \( \sqrt{5} \)’s pop out naturally, taking away some of the mystery of the cool formula.

The nth term of a Fibonacci series.

November 13, 2020 math and physics play , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post.]

I’ve just started reading [1], but already got distracted from the plot by a fun math fact. Namely, a cute formula for the nth term of a Fibonacci series. Recall

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

We can quickly find that the series has values \( 0, 1, 1, 2, 3, 5, 8, 13, \cdots \). What’s really cool, is that there’s a closed form expression for the nth term in the series that doesn’t require calculation of all the previous terms.

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

This is a rather miraculous and interesting looking equation. Other than the \(\sqrt{5}\) scale factor, this is exactly the difference of the nth powers of the golden ratio \( \phi = (1+\sqrt{5})/2 \), and \( 1 – \phi = (1-\sqrt{5})/2 \). That is:
\begin{equation}\label{eqn:fibonacci:60}
F_n = \frac{\phi^n – (1 -\phi)^n}{\sqrt{5}}.
\end{equation}

How on Earth would somebody figure this out? According to Tattersal [2], this relationship was discovered by Kepler.

Understanding this from the ground up looks like it’s a pretty deep rabbit hole to dive into. Let’s save that game for another day, but try the more pedestrian task of proving that this formula works.

Start proof:

\begin{equation}\label{eqn:fibonacci:80}
\begin{aligned}
\sqrt{5} F_n
&=
\sqrt{5} \lr{ F_{n-2} + F_{n-1} } \\
&=
\phi^{n-2} – \lr{ 1 – \phi}^{n-2}
+ \phi^{n-1} – \lr{ 1 – \phi}^{n-1} \\
&=
\phi^{n-2} \lr{ 1 + \phi }
-\lr{1 – \phi}^{n-2} \lr{ 1 + 1 – \phi } \\
&=
\phi^{n-2}
\frac{ 3 + \sqrt{5} }{2}
-\lr{1 – \phi}^{n-2}
\frac{ 3 – \sqrt{5} }{2}.
\end{aligned}
\end{equation}
However,
\begin{equation}\label{eqn:fibonacci:100}
\begin{aligned}
\phi^2
&= \lr{ \frac{ 1 + \sqrt{5} }{2} }^2 \\
&= \frac{ 1 + 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 + \sqrt{5} }{2},
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:fibonacci:120}
\begin{aligned}
(1-\phi)^2
&= \lr{ \frac{ 1 – \sqrt{5} }{2} }^2 \\
&= \frac{ 1 – 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 – \sqrt{5} }{2},
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:140}
\sqrt{5} F_n = \phi^n – (1-\phi)^n.
\end{equation}

End proof.

References

[1] Steven Strogatz and Don Joffray. The calculus of friendship: What a teacher and a student learned about life while corresponding about math. Princeton University Press, 2009.

[2] James J Tattersall. Elementary number theory in nine chapters. Cambridge University Press, 2005.