What is $x$ of the $m$-Fibonacci complexity $O(x^n)$ as $m \rightarrow \infty$? I was helping a colleague (we're both tertiary students) with a computer science question. The question requires analysing the time complexity of various Fibonacci algorithms. One is the slow recursive way where the same subproblems are recalculated. Another modifies the algorithm to instead have three base cases and three recursive calls:
fib3(n)
    if n = 0 then
        return 0
    else if n = 1 or n = 2 then
        return 1
    else
        return fib3(n-1) + fib3(n-2) + fib3(n-3)
    end
end

We know that the time complexity of the Fibonacci sequence using a recursive approach without memoization is $O(\Phi ^ n)$ for $n > 2$.
Proof: since $fib(n) = fib(n-1) + fib(n-2)$, we know using a recursion tree that

*

*each node has a branching factor of 2, excluding the leaf nodes,

*The height is $n$ (path from root, always taking the $fib(n-1)$ option), and

*The shortest path from root to leaf is $n/2$ (always taking the $fib(n-2)$ option).

Hence, the time complexity is $T(n) = cx^n = cx^{n-1} + cx^{n-2}$, s.t. $c > 0$ and $1 < x < 2$. Dividing by $cx^{n-2}$,
$$\begin{aligned}
x^2 &= x + 1 \\\\
0 &= x^2 - x - 1 \\\\
x &= \frac{1 + \sqrt{5}}{2} \approx 1.62
\end{aligned}$$
Extending this to the fib3(n) algorithm, we have $0 = x^3 - x^2 - x - 1$. Using the solve for function in Symbolab, we have $x \approx 1.84$, which is lower than I expected as the branching factor is 3 for most nodes.
This led me to test if $x < 2$ for all values of $m$ where
$$fib_m(n) = \sum_{i=1}^m fib_m(n-i)$$
I got the following results:




m
x (2 d.p.)




2
$\Phi$


3
1.84


4
1.93


5
1.97


6
1.98




I haven't proved this hypothesis, so I'm wondering if somebody has already proved that $\lim_{m \rightarrow \infty} O(fib_m(n)) = 2^n$. If so, please answer with the DOI/URL.
NOTE: I don't know if this more generalised version of the Fibonacci sequence has a name, so I'm just calling it $fib_m(n)$.
 A: This is not hard to see with a bit of calculus.
Because $x^n-(1+x+\ldots+x^{n-1})=x^n-\frac{x^n-1}{x-1}=\frac{x^{n+1}-2x^n+1}{x-1}$, we can analyse the zeros of $x^n-(1+x+\ldots+x^{n-1})$ by analysing zeros of $f(x)=x^{n+1}-2x^n+1$. The derivative of the latter is $f'(x)=(n+1)x^n-2nx^{n-1}=x^{n-1}((n+1)x-2n)$, which has a zero at $x=\frac{2n}{n+1}=2-\frac{2}{n+1}$. This lets us check the behaviour of $f(x)$ for $x\ge 1$:

*

*$f(1)=0$

*$f(x)$ is decreasing for $1\le x\le 2-\frac{2}{n+1} $, reaching a (negative) minimum at $x=\frac{2}{n+1}$, and then increasing for $x\ge2-\frac{2}{n+1}$

*$f(2)=2^{n+1}-2\cdot 2^n+1=1$ - positive.

Thus, on $x\gt 1$, the function $f$ has one zero, which is between $2-\frac{2}{n+1}$ and $2$.
This zero is then the largest positive solution of the original equation $x^n-(1+x+\ldots+x^{n-1})=0$ and is the one that features in your complexity calculations. As per squeeze theorem, this zero converges to $2$ when $n\to\infty$, being "squeezed" between $2-\frac{2}{n+1}$ and $2$.
A: If $x_m$ is the desired root and $z_m=1/x_m$, then $0<z_m<1$ and
$P_m(z_m)=0$, where $P_m(z)=1-z-z^2-\dots-z^m$. Then $z_m$ is a strictly decreasing sequence,
and the limit $z_\infty$ satisfies
$1=z_\infty+z_\infty^2+z_\infty^3+\dots$, whence $z_\infty=1/2$.
To get a rigorous bound on the rate of convergence, observe that
$|P_m'(z)| \ge 1$ for $z>0$, so for some intermediate point $\xi_m \in (1/2,z_m)$, we have
$$2^{-m}=|P_m(1/2)-P_m(z_m)| =|P_m'(\xi_m)| \cdot |z_m-1/2| \ge |z_m-1/2|\,.$$
