Message Boards Message Boards

[✓] Ratios in expanded Fibonacci series?

GROUPS:

My father is interested in a formula for the ratio of "expanded" Fibonacci series. The "normal" series adds 2 numbers together (1,1,2,3,5...). The ratio is 1.61803398... By adding 3 numbers together, regardless of the initial three numbers, the ratio is 1.83928... By adding 4 numbers together, the ratio is 1.9275620... And so on. The formula for normal Fibonacci numbers is (1+SQRT 5)/2. What is the formula for "expanded" series?

POSTED BY: Mark Good
Answer
1 month ago

Probably not so simple

In[3]:= sln = 
 RSolve[{a[n] == a[n - 1] + a[n - 2], a[1] == a[2] == 1}, a[n], n]

Out[3]= {{a[n] -> Fibonacci[n]}}

In[4]:= sln1 = 
 RSolve[{a[n] == a[n - 1] + a[n - 2] + a[n - 3], 
   a[1] == a[2] == a[3] == 1}, a[n], n]

Out[4]= {{a[n] -> 
   Root[-1 - #1 - #1^2 + #1^3 &, 1]^
     n Root[-1 + #1 + 11 #1^2 + 11 #1^3 &, 1] + 
    Root[-1 - #1 - #1^2 + #1^3 &, 3]^
     n Root[-1 + #1 + 11 #1^2 + 11 #1^3 &, 2] + 
    Root[-1 - #1 - #1^2 + #1^3 &, 2]^
     n Root[-1 + #1 + 11 #1^2 + 11 #1^3 &, 3]}}
POSTED BY: Frank Kampas
Answer
1 month ago

The MathWorld entries for the tribonacci number, tribonacci constant, and Fibonacci $n$-step number are quite informative on the subject of linear recurrences that generalize the usual Fibonacci sequence. I will only add in addition to Frank's answer that you can use DifferenceRoot[] directly:

tribonacci = DifferenceRoot[Function[{a, n}, {a[n] == a[n - 1] + a[n - 2] + a[n - 3],
                                              a[1] == 1, a[2] == 1, a[3] == 1}]];

and then use it in Limit[] (with some help from FunctionExpand[] and ToRadicals[]):

Limit[tribonacci[n + 1]/tribonacci[n] // FunctionExpand, n -> ∞] // ToRadicals
   (1 + (19 - 3 Sqrt[33])^(1/3) + (19 + 3 Sqrt[33])^(1/3))/3

N[%, 30]
   1.83928675521416113255185256465
POSTED BY: J. M.
Answer
1 month ago

RSolve works also, although it gives a more complex expression

In[20]:= sln = 
  RSolve[{a[n] == a[n - 1] + a[n - 2] + a[n - 3], 
    a[1] == a[2] == a[3] == 1}, a[n], n];

In[21]:= f[n_] = a[n] /. sln[[1]] // ToRadicals;

In[22]:= lim = Limit[f[n + 1]/f[n], n -> \[Infinity]]

Out[22]= (-22 2^(5/6) + 4 Sqrt[11] (283 + 21 Sqrt[33])^(1/6) + 
   2 2^(2/3) Sqrt[11] (259 + 45 Sqrt[33])^(1/6) - 
   11 (329 + 57 Sqrt[33])^(1/6) + 
   2 Sqrt[22 (7 - Sqrt[33])] (329 + 57 Sqrt[33])^(1/6) + 
   2 Sqrt[22 (7 + Sqrt[33])] (329 + 57 Sqrt[33])^(1/6) - 
   11 2^(1/6) (329 + 57 Sqrt[33])^(1/3) + 
   2^(1/3) Sqrt[11] (26803 + 4611 Sqrt[33])^(1/6) + 
   2^(2/3) Sqrt[11] (8745739 + 1522395 Sqrt[33])^(
    1/6))/(3 (329 + 57 Sqrt[33])^(
   1/6) (-11 + Sqrt[11] (566 - 42 Sqrt[33])^(1/6) + 
     Sqrt[11] (566 + 42 Sqrt[33])^(1/6)))

In[23]:= N[lim, 30]

Out[23]= 1.83928675521416113255185256465
POSTED BY: Frank Kampas
Answer
1 month ago

Yes, RSolve[] also works:

f = RSolveValue[{a[n] == a[n - 1] + a[n - 2] + a[n - 3], a[1] == a[2] == a[3] == 1}, a, n];
Limit[f[n + 1]/f[n], n -> ∞] // RootReduce // ToRadicals
   (1 + (19 - 3 Sqrt[33])^(1/3) + (19 + 3 Sqrt[33])^(1/3))/3
POSTED BY: J. M.
Answer
1 month ago

There does seem to be a pattern

In[15]:= f3 = 
  RSolveValue[{a[n] == a[n - 1] + a[n - 2] + a[n - 3], 
    a[1] == a[2] == a[3] == 1}, a, n];
Limit[f3[n + 1]/f3[n], n -> \[Infinity]] // RootReduce

Out[16]= Root[-1 - #1 - #1^2 + #1^3 &, 1]

In[17]:= f4 = 
  RSolveValue[{a[n] == a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4], 
    a[1] == a[2] == a[3] == a[4] == 1}, a, n];
Limit[f4[n + 1]/f4[n], n -> \[Infinity]] // RootReduce

Out[18]= Root[-1 - #1 - #1^2 - #1^3 + #1^4 &, 2]
POSTED BY: Frank Kampas
Answer
1 month ago

Yes, the pattern is related to the fact that the polynomials showing up in the Root[] expressions are precisely the characteristic polynomials associated with the linear recurrence. This is all explained in the MathWorld link I gave in an earlier post.

POSTED BY: J. M.
Answer
1 month ago

I just looked at the article but wonder if there is a general derivation for the limit of the ratio.

POSTED BY: Frank Kampas
Answer
1 month ago

Here is a rough sketch, which can be made rigorous by somebody determined: the $n$-nacci numbers, as the solutions of a linear difference equation, can be expressed as linear combinations of powers of the roots of the corresponding characteristic polynomial.

To give a more concrete example, let's look at the usual Fibonacci sequence (and is easily generalized to the higher-order versions). Since we have the relation

$$f_{n}-f_{n-1}-f_{n-2}=0$$

then the characteristic polynomial is

$$x^2-x-1$$

(notice the correspondence?), whose roots are $\phi$ and $-\frac1{\phi}$. So, the Fibonacci (and thus the Lucas numbers as well) are expressible as

$f_n=A\phi^n+B\left(-\frac1{\phi}\right)^n$

where constants $A$ and $B$ can be determined from the initial conditions given. In particular, these characteristic polynomials have only one positive root $\chi$ ( $\chi=\phi$ in the Fibonacci case), so asymptotically $f_n\approx\chi^n$. So, the limit you are taking is effectively

$$\lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\lim_{n\to\infty}\frac{\chi^{n+1}}{\chi^n}=\chi$$

POSTED BY: J. M.
Answer
1 month ago

Thank you. Your comments have helped us out. My father will be 99 in two months and is celebrating his 75 wedding anniversary with my mother this week. He was a research physicist and I graduated from Cornell with a major in mathematics years ago. He continues to work on math problems as a hobby.

POSTED BY: Mark Good
Answer
1 month ago

Group Abstract Group Abstract