# Fibonacci Numbers: Did Fibonacci just come up with the sequence as a lark? Or, did he derive it from something else? **URL:** \ **Category:** Factual Questions\ **Created:** [November 6, 2021, 7:12am UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879 "2021-11-06T07:12:53Z")\ **Posts on this page:** 8\ **Page:** 2
**Author:** ![Saffer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saffer/32/6440_2.png) [@Saffer](https://boards.straightdope.com/u/Saffer)\ **Post date:** [November 16, 2021, 2:53pm UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/21 "2021-11-16T14:53:43Z")
[Here](https://gist.github.com/rflechner/2b59e81381bc59306dff9cc4147d4f18) you can find 3 implementations of Fibonacci, in F#. The first is naively recursive which exhibits the poor performance you mentioned. The last is tail recursive which does not. ---
**Author:** ![Saffer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saffer/32/6440_2.png) [@Saffer](https://boards.straightdope.com/u/Saffer)\ **Post date:** [November 16, 2021, 2:59pm UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/22 "2021-11-16T14:59:05Z")
Now that we seem to have gone a little off piste here, anyone who is unsure about the benefits of tail call optimization might want to check out this recent article: [Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C](https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html) ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [November 17, 2021, 4:14am UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/23 "2021-11-17T04:14:24Z")
Consider the task of computing an (for positive integers n) using simple repetitive multiplication, e.g., compute a4 simply as a product: aaaa Now consider that multiplication is associative, so you could compute that as: ((((a)a)a)a) or: (a(a(a(a)))) or: (aa)(aa) or: (a(aa)a) etc. How many distinct ways could you parenthesize that? How many distinct ways could you parenthesize an when written out that way? I devised an algorithm for that once, and coded it in C both iteratively and recursively, and ran this on a 80386. The recursive version slowed down noticeably at about a6 and took many minutes to run for (IIRC) a10 and crashed at about a12. The iterative version ran in less than one second for values up to ahuge. (The algorithm inherently produced lots of duplicates, so there was additional code to compare each result with previous results to filter out the duplicates.) ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [November 17, 2021, 4:21am UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/24 "2021-11-17T04:21:33Z")
I did that for Ackerman’s Function once also, many years ago, using a CDC-6400 computer which had 60-bit integers. The recursive definition could only compute up to about A(3) in any reasonable amount of time. I figured out how to do it iteratively, and got up to something like a(6) or so, before it overflowed the 60-bit integer limit, but the computation was very fast. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [November 17, 2021, 6:26pm UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/25 "2021-11-17T18:26:40Z")
Those numbers are called the Catalan numbers (not after Catalonia, but a mathematician of that name). The n-th Catalan number is C\_n=\frac{(2n)!}{n!(n+1)!}. They satisfy the recursion equation C\_n=\sum\_{i=1}^{n-1}C\_iC\_{n-i} which expresses the fact that you have to start with an “outer multiplication” of a term of length i by one of length n-i. If you form the formal power series f(x)=\sum\_{i=1}^{\infty}C\_ix^i, then use the recursion above to derive xf(x)^2=1+f(x) and use the quadratic formula to get an expression involving \sqrt(1-4x), which can calculated using the generalized binomial theorem (for the fractional exponent 1/2 to produce, eventually, the formula above. There is more detail in the Wiki entry, q.g. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 17, 2021, 8:43pm UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/26 "2021-11-17T20:43:29Z")
Using that formula, you can clearly compute the exact value of C\_n via a simple loop like C\_5 = \frac72 \times \frac83 \times \frac 94 \times \frac{10}{5} but can one do better? ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [November 18, 2021, 3:13am UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/27 "2021-11-18T03:13:33Z")
> **[Why Names Matter](https://mathenchant.wordpress.com/2021/11/16/why-names-matter/)** > > I just went through my lesson plan for an upcoming lecture on number-sequences and replaced the name “Fibonacci” by the name “Hemachandra”. By the time you finish reading th… ---
**Author:** ![Wendell\_Wagner](https://avatars.discourse-cdn.com/v4/letter/w/8491ac/32.png) [@Wendell\_Wagner](https://boards.straightdope.com/u/Wendell_Wagner)\ **Post date:** [November 19, 2021, 9:16am UTC](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879/28 "2021-11-19T09:16:40Z")
Bizarrely, I did something like this renaming in my only published mathematical article. It appeared in the _Journal of Undergraduate Mathematics_ (Volume 7, Number 1), which was published in March of 1975. This journal no longer exists and was pretty obscure anyway. I talked about a generalization of Pascal’s triangle. Pascal’s triangle was known long before Blaise Pascal. One of those who knew about it was Omar Khayyam. My paper was about the n-dimensional generalization of Pascal’s triangle. I called them Khayyamic n-simplices. The paper was titled “Khayyamic n-simplices: a generalization of Pascal’s triangle”. [Previous page](https://boards.straightdope.com/t/fibonacci-numbers-did-fibonacci-just-come-up-with-the-sequence-as-a-lark-or-did-he-derive-it-from-something-else/953879.md?page=1)