1
$\begingroup$

One of the most important generalization of the classical Fibonacci numbers is the Fibonacci $p$-step numbers that is defined as follows

\begin{equation}\label{cp26} F_n^{(p)}=F_{n-1}^{(p)}+F_{n-2}^{(p)}+\cdots+F_{n-p}^{(p)}\, . \end{equation}

With boundary conditions

$$F_{0}^{(p)}=0\quad , \quad F_{1}^{(p)}=0\quad ,\, \cdots\, ,\quad F_{p-2}^{(p)}=0\quad , \quad F_{p-1}^{(p)}=1\, .$$

We can get the limit value of Fibonacci $p$-step numbers by inverse of solution of equation $x^{p+1}-2\, x+1=0$ in the interval $(0,1)$. We denote the limit value of Fibonacci $p$-step numbers with $\alpha_p$. In fact, $\alpha_p$ is defined in the following form $$ \alpha_p=\displaystyle{\lim_{n\rightarrow\infty}}\quad \frac{F^{(p)}_{n+1}}{F^{(p)}_{n}}~. $$

We denote the length of $ F_n^{(p)}$ number with $L_n^{(p)}$. For example, $ F_{10}^{(2)}=55$ therefore $L_{10}^{(2)}=2$. With simulation, I found the following connection between the length of Fibonacci $p$-step numbers and its limit values $$ \mid \frac{F^{(p)}_{n+1}}{F^{(p)}_{n}}-\alpha_p\mid \, \approx \, 10^{-{\displaystyle{L_n^{(p)}(\frac{p}{p-1})}}}~. $$
I make some examples to clarify what i mean. For $p=2$, the Fibonacci $2$-step number is the classical Fibonacci number. The limit value of the Fibonacci $2$-step number is inverse of solution of equation $x^3-2\, x+1=0$ in the interval $(0,1)$. so, for $p=2$, the limit value is

\begin{eqnarray} \alpha_2= \frac{1}{0.61803398874989484820458683436563811772030917980580}& & \\ & & \\ = 1.6180339887498948482045868343656381177203091798058~.& & \end{eqnarray}

The length of $F_{72}^{(2)}$ and $ F_{73}^{(2)}$ are $15$. With calculation, we have the following relation

$$ \mid \frac{F^{(2)}_{73}}{F^{(2)}_{72}}-\alpha_2\mid= \mid \frac{ 806515533049393}{ 498454011879264}-\alpha_2\mid \, \approx \, 10^{-30}~. $$
For $p=3$, the Fibonacci $3$-step number is called Tribonacci number. The limit value of the Fibonacci $3$-step number is inverse of solution of equation $x^4-2\, x+1=0$ in the interval $(0,1)$.

\begin{eqnarray} \alpha_3= &1.8392867552141611325518525646532866004241787460975 & \\ & 92246778758639404203222081966425738435419428307014& ~. \end{eqnarray}

The length of $F_{113}^{(3)}$ and $ F_{114}^{(3)}$ are $30$. With calculation, we have the following relation

$$ \mid \frac{F^{(3)}_{114}}{F^{(3)}_{113}}-\alpha_3\mid= \mid \frac{270409000010299937423541789777}{ 147018402238651639664609196920}-\alpha_3\mid \, \approx \, 10^{-45}~. $$ Is there a analytical method that we can proof the mentioned formula. I would greatly appreciate for any suggestions.

$\endgroup$
2
$\begingroup$

I think most (all?) of this follows from basic properties of linear recurrences. The characteristic polynomial of your $p$-step Fibonacci numbers is $x^p-x^{p-1}-x^{p-2}-\cdots-x-1$. You seem to have multiplied that by $x-1$ to get $x^{p+1}-px+1$. So for example, for $p=2$, instead of the usual $x^2-x-1$, which has as its roots the golden ratio and its conjugate, $\frac12(1+\sqrt5)$, you instead have $x^3-2x+1=(x-1)(x^2-x-1)$. Anyway, your $\alpha_2$ is the golden ratio. In general, your $F_n^{(p)}$ has the form $\sum c_{p,i} \beta_{p,i}^n$, where the $\beta_{p,i}$ are the roots of the characteristic polynomial. What you're calling the "Fibonacci $p$-step number" is, I think, just the largest root of the characteristic polynomial.

$\endgroup$
  • $\begingroup$ Excuse me Professor Silverman, I think If you multiplied by $x-1$, we get $x^{p+1}-2\,x^p+1$. If you like I edit my question to show that how can I obtained $x^{p+1}-2\,x+1$. If you have a time, I suggest to see this post, maybe you find it interesting. Thanks for answer. $\endgroup$ – Amin235 May 8 '17 at 13:59
  • 1
    $\begingroup$ @Amin235 Good point, you're using the reciprocal polynomial, i.e., the "reciprocal" of a degree $d$ poly $f(x)$ is $x^df(1/x)$. So you've switched the roots with their reciprocals, and maybe (? I haven't checked) your Fibonacci $p$-step number is actually the reciprocal of the smallest root of the characteristic poly. $\endgroup$ – Joe Silverman May 8 '17 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.