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

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!)

-
So, this is the question after the final question? –  Gerry Myerson Jan 22 '13 at 3:15
@GerryMyerson I felt that it was just too clustered within the last question to include this one. I felt it would be better to ask it seperately. This question relates fully to the other one. Also, "The Final Question" refers to number 5 in the problem set. –  Anthony Peter Jan 22 '13 at 3:20

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$.

-
So would this be a suitable proof to use in my paper? If I want to use the original post as a lemma I mean –  Anthony Peter Jan 22 '13 at 4:37
The first question, Anthony, is: do you understand it? If not, then it certainly isn't a suitable proof to use. –  Gerry Myerson Jan 22 '13 at 5:02

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$.

-
Where does the $x^n-x^{n-1}-x^{n-2}-\cdots-x^2-x-1=0$ polynomial come from? –  Anthony Peter Jan 22 '13 at 3:02
@Anthony: It’s the characteristic polynomial of the recurrence. –  Brian M. Scott Jan 22 '13 at 3:56
Anthony, I am not interested in entering into email correspondence with you. –  Gerry Myerson Jan 22 '13 at 6:20
@GerryMyerson The condescending attitude is rather off-putting. But it's alright, I guess some people are nicer than others. –  Anthony Peter Jan 22 '13 at 6:46
@AnthonyPeter: Gerry does not sound condescending. He is simply letting you know that he won't be corresponding with you via email. –  robjohn Jan 23 '13 at 2:43