Message Boards Message Boards

1
|
6363 Views
|
9 Replies
|
16 Total Likes
View groups...
Share
Share this post:

[?] Ratios in expanded Fibonacci series?

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
9 Replies

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
Posted 7 years 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.

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
Posted 7 years 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.

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
Posted 7 years 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.

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

POSTED BY: Frank Kampas
Posted 7 years 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.

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
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract