The Fibonacci sequence is the most famous example of a generalised sequence that begins with two seed numbers \( a \) and \( b \) and then proceeds as follows:$$ G_n=\begin{cases}a&\mbox{if }n=0;\\b&\mbox{if }n=1;\\G_{n-1}+G_{n-2}&\mbox{otherwise.}\end{cases} $$So \(G_3=b+a \), \(G_4=a+2b \) etc. It can be shown that the \(n\)-th term in the Fibonacci sequence is given by \( [ \phi ]^n/ \sqrt 5 \) (where the square brackets denote rounding to the nearest whole number) and so the question could be asked is there a general formula for calculating the \(n\)-th term of the generalised sequence \(a, b, a+b, a+2b, ... \)? Well, after watching this Numberphile video, it turns out that there is:
The formula is:$$G_n=\bigg [ \phi ^n \times \frac{(3 \sqrt 5 - 5) \, a + (5 - \sqrt 5) \, b}{10} \bigg ] $$When \(a=1\) and \(b=1\), we get \( [ \phi ]^n/ \sqrt 5 \) so all is well. When \(a=1 \) and \(b=3 \), we get simply \( [ \phi ]^n \) and this generates the Lucas numbers: 1, 3, 4, 7, 11, ...
The Numberphile video makes the point that it is the number \( \sqrt 5 \) that is at the heart of this formula and thus underlies all these Fibonacci-like sequences that are generated from two seed numbers.
We can also consider not two but three seed numbers and this leads to what is called the Tribonacci sequence defined by:$$
T_n=\begin{cases}0&\mbox{if }n=0\\1&\mbox{if }n=1\\1&\mbox{if }n=2\\T_{n-1}+T_{n-2}+T_{n-3}&\mbox{if }n \geq 3\end{cases}
$$This leads to 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ... and, just as the closed-form formula for the Fibonacci sequence involved the roots of the polynomial \(x^2-x-1\), it is reasonable to expect that the analogous formula for the tribonacci sequence involves the polynomial \(x^3-x^2-x-1\) and this is indeed the case. This polynomial has one real root:$$ \frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929 $$ called the tribonacci constant and this is the ratio of successive pairs of terms. In other words:$$
\lim_{n \to \infty} \frac {T_{n+1}}{T_n}=\frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929
$$The other two roots are complex conjugates (source). The generating function for the tribonacci numbers is quite similar to the generating function for the Fibonacci numbers:$$ \sum_0 ^ \infty \! T_n \, x^n = \frac {x}{1-x-x^2-x^3} $$
We can also consider not two but three seed numbers and this leads to what is called the Tribonacci sequence defined by:$$
T_n=\begin{cases}0&\mbox{if }n=0\\1&\mbox{if }n=1\\1&\mbox{if }n=2\\T_{n-1}+T_{n-2}+T_{n-3}&\mbox{if }n \geq 3\end{cases}
$$This leads to 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ... and, just as the closed-form formula for the Fibonacci sequence involved the roots of the polynomial \(x^2-x-1\), it is reasonable to expect that the analogous formula for the tribonacci sequence involves the polynomial \(x^3-x^2-x-1\) and this is indeed the case. This polynomial has one real root:$$ \frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929 $$ called the tribonacci constant and this is the ratio of successive pairs of terms. In other words:$$
\lim_{n \to \infty} \frac {T_{n+1}}{T_n}=\frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929
$$The other two roots are complex conjugates (source). The generating function for the tribonacci numbers is quite similar to the generating function for the Fibonacci numbers:$$ \sum_0 ^ \infty \! T_n \, x^n = \frac {x}{1-x-x^2-x^3} $$
No comments:
Post a Comment