# The connection between the length of Fibonacci $p$-step numbers and its limit values

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

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

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.

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.
• 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. – Amin235 May 8 '17 at 13:59
• @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. – Joe Silverman May 8 '17 at 15:08