Skip to content

The Fibonacci sequence, under duress

May 14, 2013

Physics and math have a complicated relationship, and I mean that in almost exactly the same way that your Facebook friends mean it.

its_complicated

Allow me to elaborate.

One very legitimate way to view mathematics is as the exploration of a pristine and entirely non-physical universe of numbers and relationships.  In this view, which is largely the view of the academic mathematician, the universe of math exists in parallel to our own, real, universe.  Each mathematical theorem is a discovery of some feature of that universe, and its correctness does not depend in any way on the physical features of reality.  [In the (paraphrased) words of G.H. Hardy, it is true that 2 + 3 = 5, regardless of whether you think "2" stands for "two apples" or "two pennies", or anything else.]   In other words, pure mathematics exists completely independently of the human brain and its interests, and mathematicians are merely its explorers.

Physics, on the other hand, is a much more blue-collar pursuit.  The goal of physics is only to describe past observation so that we can predict the outcome of future observations.  Of course, such predictions can bring a tremendous amount of practical power, and they provide the foundation for nearly all technological innovation.  Physics can also be tremendously interesting, and even aesthetically pleasing (at least to suitably eccentric people like myself).  Still, by design physics makes no claim about absolute or human-independent truth, and indeed, the idea of truth outside of observable reality is fundamentally abhorrent to the discipline of physics.

Given this difference in philosophy, it may seem odd that physics has been so hopelessly entangled with mathematics for hundreds of years.  The reason for this extended liaison can be seen as a consequence of the remarkable parallels that keep emerging between our own real universe and the mathematical universe.  The discoveries of mathematicians keep proving to be useful, for no particularly apparent reason, in creating descriptions of the real universe, and so we continue to exploit them.  Still, to a physicist, there is nothing sacred about the use of mathematics.  Math is a tool that is useful only insomuch as it can be used as a highly-accurate metaphor for physical reality.  Math deals only with exact statements about a “fictitious” universe.  But physics must make approximate statements about a “real” universe.  If getting a useful descriptive/predictive statement requires abusing the purity and exactitude of mathematics along the way, then so be it.

In short, physicists view math in much the same way that politicians view philosophy.  You use it earnestly when you can, and you twist it to suit your own purposes when you can’t.

Part of becoming a physicist is learning to get comfortable with this ethos of exploitation, to one degree or another.  One has to get “familiar” with abuses of mathematics, and develop “intuition” as to how far it can be stretched before it yields, under duress, an answer that is wrong, or worse, not even wrong.

\hspace{1mm}

Lately I’ve been on a streak of talking about examples where “intuitive” manipulation of mathematics can lead to answers while straightforward calculation is difficult (namely, integrating sin(x) to infinity and deriving the Pythagorean theorem).  In this post I thought I would share one more of my favorite abuses of mathematics.  This is a derivation of the formula for the Fibonacci sequence.

Fibonacci Pineapples_0026

Calculating the Fibonacci sequence.

[I apologize if what follows is a bit stream-of-consciousness-y, but I thought it might help to illustrate the sort of intuitive line of thinking that one (I, at least) would actually follow to get the answer.]

The Fibonacci sequence, in case you have never encountered it, is the sequence of numbers that results from writing first 0 and 1, and then adding the previous two numbers to get the next one in the sequence.  The resulting sequence goes on like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Famously, as you go to high numbers in the sequence, the ratio of two successive numbers approaches the golden ratio

\varphi = (1 + \sqrt{5})/2 \approx 1.618.

What is perhaps less well-known is that you don’t have to count through the sequence one number at a time in order to figure it out.  There is a simple formula, f(n), for the sequence, which can tell you any term that you want to know.  For example, I can say without doing any tedious addition that the 91st term of the Fibonacci sequence is 4,660,046,610,375,530,309 (about 4 quintillion).

If you want to derive this sequence f(n) the way a physicist would, you should start with the following two steps:

1) Write down the exact relation that defines the sequence:  f(n) = f(n-1) + f(n-2).

2) Squint at it until it starts to look like something you already know how to deal with.

In my own personal case, this “squinting” involves thinking about what happens when n gets really large.  Clearly, at large n the sequence f(n) grows very quickly; by n = 91, f(n) is already at 4 quintillion!  Usually, when something grows that quickly, it means there is some kind of exponential dependence.  Exponential dependencies arise when your rate of growth is proportional to your size (just like logarithmic dependencies arise when your rate of growth is inversely proportional to your size).  So now there is a lead to follow: is the rate of growth of f(n) in fact proportional to its own value?

In fact, it is, and the simple way to see this is by first replacing n-1 by n in the definition of the sequence above, so that you have

f(n) = f(n+1) - f(n-1).

Now, if you really consider n to be large, then you can think of n \pm 1 as n \pm \delta n, where \delta n is something small (compared to n).  Then the right-hand side of the equation above really looks like a derivative: f(n+1) - f(n-1) =[f(n+\delta n) - f(n - \delta n)]/(\delta n).  This is all the evidence that you need to confirm your suspicion that f(n) is indeed proportional to its own derivative, at least at large n, and so it should be exponential.

Now you can make an educated guess for f(n): it should be something exponential, like f(n) = A e^{k n}, where A and k are some unknown constants.  This means f(n+1) = A e^{k} e^{k n} and f(n-1) = A e^{-k} e^{k n}.  Put these into the equation above, and what you’ll find is

1 = e^{k} - 1/e^{k}.

You can solve for k, but it’s actually more interesting (and easy) to solve directly for e^k.  You can use the quadratic equation for this, and what you find is that there are two solutions:

e^k = (1 \pm \sqrt{5})/2.

The first one of those two solutions (the plus sign), is the golden ratio, \varphi!  I hope this gives you another feeling of being on the right track.

The fact that there are two solutions for e^k — let’s call them \varphi = (1 + \sqrt{5})/2 \approx 1.618 and \psi = (1 - \sqrt{5})/2 \approx -0.618 — means that there are two different kinds of solutions for the governing equation f(n) = f(n+1) - f(n-1).  Namely, these solutions are A \varphi^n and B \psi^n.  Any combination of these two satisfies the same “Fibonacci relation”, so you can write

f(n) = A \varphi^n + B \psi^n.

Now all that’s left is to figure out the values of A and B by applying the conditions f(0) = 0 and f(1) = 1.  This process gives the final result:

f(n) = (\varphi^n - \psi^n)/\sqrt{5}.

\hspace{1mm}

So there you have it.  Now you can impress your friends by telling them that the 1776th Fibonacci number is approximately 4.5 \times 10^{370}.

You can also see why the ratio of two successive Fibonacci numbers at large n gives you the golden ratio: since \psi is smaller than 1, at large n its contribution gets completely eliminated from the sequence, and all you’re left with is f(n) \sim \varphi^n, so that f(n+1)/f(n) \sim \varphi.

\hspace{1mm}

\hspace{1mm}

Footnotes

1.  You can make your own “pseudo-Fibonacci” sequence by starting with any two numbers of your choosing, rather than 0 and 1, and then following the rule of adding the previous two to get the next number.  The same formula as above will hold, except that the coefficients A and B will be different.  And the ratio of two subsequent pseudo-Fibonacci numbers will still be equal to \varphi (regardless of whether you choose to start your sequence with positive, negative, or even imaginary numbers).

2.  It is perhaps funny to notice that since \psi is negative, the quantity \psi^n only gives a real answer when n is an integer.  That means that if you think of f(x) as a continuous function, then its value lives in the complex plane and only crosses the real axis when x is an integer.  Like this.

UPDATE:

3.  The fact that f(n) is not real at non-integer n means that if someone asks you “what’s the 1.5th term of the Fibonacci sequence?”, you can answer “0.92 + 0.22 i”.

4. You may have noticed that when I wrote f(n) =[f(n+\delta n) - f(n - \delta n)]/(\delta n), the right-hand side looks like twice the derivative.  This means that at large n you should have f(n) \approx 2 f'(n).  In fact, if you work it out, the exact answer is f(n) = f'(n)/\ln(\varphi) \approx 2.07 f'(n).

5.  If I were only slightly less mature, the second sentence of this post would have been:

Namely, Physics uses Math for \int e^x.

About these ads
5 Comments leave one →
  1. jacobus permalink
    May 14, 2013 9:44 pm

    Excellent post. If only you hadn’t just missed Fibonacci day: 5-8-13.

  2. May 15, 2013 4:02 am

    16MB 3744×5616 photo looks a bit too large ;)

    • Brian permalink*
      May 15, 2013 7:54 am

      Good point! It should be fixed now.

  3. May 15, 2013 11:58 am

    Great post, so glad you’ve come back! Thanks.

  4. May 30, 2013 12:23 am

    Maths is like stitched clothes that never fit physics perfectly,can cover it only approximately.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 107 other followers

%d bloggers like this: