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

@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 03:20

score 2 · Answer 1 · answered Jan 22 '13 at 02:58

2

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

answered Jan 22 '13 at 02:58

Gerry Myerson

179,216

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 03:02
@Anthony: It’s the characteristic polynomial of the recurrence. – Brian M. Scott Jan 22 '13 at 03:56
@BrianM.Scott If I wanted to use this as a Lemma in a paper, how would I begin it's proof? – Anthony Peter Jan 22 '13 at 04:14
What is the purpose of this paper? This material is ancient history, for any purpose I can think of you wouldn't give a proof, you'd give a reference to a textbook where it's covered. Are you writing a textbook? – Gerry Myerson Jan 22 '13 at 05:01
@GerryMyerson The paper is not about this above proof. It's just a lemma for a paper. – Anthony Peter Jan 22 '13 at 05:05
My remark still applies --- I wouldn't prove this lemma in a paper, I'd give a reference. BUt again, that depends on the nature/purpose of the paper. – Gerry Myerson Jan 22 '13 at 05:20
@Gerry Myerson I have emailed you regarding the purpose of this paper. Please let me know if you received that email – Anthony Peter Jan 22 '13 at 05:22
@GerryMyerson Note that this will be my first mathematics paper. – Anthony Peter Jan 22 '13 at 05:24
1

Anthony, I am not interested in entering into email correspondence with you. – Gerry Myerson Jan 22 '13 at 06:20
1

@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 06:46
2

@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 02:43

score 2 · Accepted Answer · answered Jan 22 '13 at 04:30

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 04: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 05:02

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

2 Answers2

Linked