Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
1  
Anthony, I am not interested in entering into email correspondence with you. –  Gerry Myerson Jan 22 '13 at 6: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 6: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 2:43
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.