Limiting Ratio of Tribonacci Numbers & Beyond

The Tribonacci series is 1, 1, 2, 4, 7, 13, 24, 44, … This article was inspired by this LinkedIn post by Fermat’s Library.

a_n = a_{n-1} + a_{n-2} + a_{n-3}

Divide both sides by a_{n-1},
\frac {a_n} {a_{n-1}} = 1 + \frac {a_{n-2}} {a_{n-1}} + \frac {a_{n-3}} {a_{n-1}}

Let the limiting ratio \frac {a_{n-1}} {a_{n}} be x.

x = \lim\limits_{n \to \infty} \frac {a_{n-1}} {a_n}

\therefore \frac 1 x = 1 + x + \lim\limits_{n \to \infty} \frac {a_{n-3}} {a_{n-1}}

\implies \frac 1 x = 1 + x + \lim\limits_{n \to \infty} \frac {a_{n-3}} {a_{n-2}+a_{n-3}+a_{n-4}}

\implies \frac 1 x = 1 + x + \lim\limits_{n \to \infty} \frac {1} {\frac {a_{n-2}}{a_{n-3}} + 1 + \frac {a_{n-4}}{a_{n-3}}}

\implies \frac 1 x = 1 + x + \frac {1} {(\frac 1 x + 1 + x)}

\implies (\frac 1 x - 1 - x) (\frac 1 x + 1 + x) = 1

\implies (1 - x - x^2) (1 + x + x^2) = 1

\implies 1 - 2x^2 -2x^3 - x^4 = 0

\implies (x^3 + x^2 + x -1) (x + 1) = 0

Obviously, x \ne -1 . Hence, x must be the real solution to the equation:

\implies (x^3 + x^2 + x -1) = 0

General Solution for ‘k’th Order Fibonacci Ratio

The above solution need not be complex, as I had overlooked the fact that

\frac {a_{n-p}} {a_{n-1}} = \frac {a_{n-p}} {a_{n-p-1}} . \frac {a_{n-p-1}} {a_{n-p-2}} ... \frac {a_{n-2}} {a_{n-1}}

\implies \frac {a_{n-p}} {a_{n-1}} = x^{p-1}

Therefore, for a ‘k’th order Fibonacci sequence,

a_n = a_{n-1} + a_{n-2} + a_{n-3} ... a_{n-k}

Divide both sides by a_{n-1},

\frac {a_n} {a_{n-1}} = 1 + \frac {a_{n-2}} {a_{n-1}} + \frac {a_{n-3}} {a_{n-1}} ...\frac {a_{n-k}} {a_{n-1}}

\implies \frac 1 x = 1 + x + x^2 + ... + x^{k-1}

Hence, x is the value for which this iteration converges:

x = \frac 1 {\sum_{i=0}^{k-1} x^i}

It is the value of the real root of

x^k + x^{k-1} + x^{k-2} + ... + x -1 = 0

Leave a Reply

Your email address will not be published. Required fields are marked *