Proof That the Ratio of Sucessive N-nacci Numbers Tends to 2.

Question

For the paper that I'm working on involving N-nacci Recursion Formulas I need to prove that $$ \lim_ {n \to \infty}\lim_{a \to \infty} \left | \frac{f^{(n)}_{a+1}}{f^{(n)}_a} \right | = 2$$
To start we know that

$$ \lim_ {n \to \infty}\lim_{a \to \infty} \left | \frac{f^{(n)}_{a+1}}{f^{(n)}_{a}} \right | = \lim_ {n \to \infty}\lim_{a \to \infty} \left | \frac{f^{(n)}_{a}+f^{(n)}_{a-1}+f^{(n)}_{a-2} + \cdots +f^{(n)}_{a-(n-1)}}{f^{(n)}_{a-1}+f^{(n)}_{a-2}+f^{(n)}_{a-3} + \cdots + f^{(n)}_{a-n}} \right | =\lim_ {n \to \infty} \lim_{a \to \infty} \left | \frac{f^{(n)}_{a-(n-1)}}{f^{(n)}_{a-n}} \right |$$ $$= \lim_ {n \to \infty}\lim_{a \to \infty} \left | \frac{f^{(n)}_{a+1}}{f^{(n)}_{a}} \right | $$ Where would I go from here?
Link to my work for my paper thus far:
N-nacci Identities: The Final Question (Generalizing Time!)

Answer 1

If $a_n$ satisfies any homogeneous constant coefficient linear recurrence, and if the characteristic polynomial for the recurrence has a unique root $\alpha$ of greatest modulus, then (unless the initial conditions are weird) $a_{n+1}/a_n\to\alpha$ as $n\to\infty$.

The root of $x^n-x^{n-1}-x^{n-2}-\cdots-x^2-x-1=0$ of greatest modulus approaches $2$ as $n\to\infty$.

Answer 2

I remember working on this at least 30 years ago - maybe more. I'll try to activate my WayBack machine.

To find (actually, estimate) the root of $f(x) = x^n-x^{n-1}-x^{n-2}-\cdots-x^2-x-1=0$:

$x^{n-1}+x^{n-2}+\cdots+x^2+x+1 = (x^n-1)/(x-1)$, so $f(x) = x^n - (x^n-1)/(x-1) = (x^{n+1}-x^n - x^n + 1)/(x-1) = (x^{n+1}-2x^n+ 1)/(x-1) $. We thus want to find out where the root of $g(x) = x^{n+1}-2x^n+ 1=0$ is.

$g'(x) = (n+1)x^n - 2n x^{n-1} = x^{n-1}((n+1)x-2n) $ so $g'(x) > 0$ for $x > 2n/(n+1) = 2-2/(n+1)$.

$g(2) > 0$ and $g(x) = x^n (x-2)+1$ so

$\begin{align} g(2-2/(n+1)) &= (2-2/(n+1))^n(-2/(n+1))+1 \\ &= -2^n(1-1/(n+1))^n (2/(n+1))+1\\ &= -2^{n+1}(n/(n+1))^n/(n+1) + 1 \\ &< -2^{n+1}/(e(n+1)) + 1 \\ &< 0 \end{align} $.

Thus $g$ (and $f$) have a root between $2$ and $2-2/(n+1)$, so the root approaches 2 for large $n$.