Asymptotic behaviour of a sequence - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:23:36Z http://mathoverflow.net/feeds/question/62394 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62394/asymptotic-behaviour-of-a-sequence Asymptotic behaviour of a sequence Nekochan 2011-04-20T11:17:37Z 2011-04-26T08:03:05Z <p>Hello, I am interested in some kind of sequence that are "not finitely recurrent".</p> <p>Let $a_i$ be a sequence taking values in ${0,1}$. Consider the sequence $(u_i)$ such that $u_0=1$, and for any positive integer $n$, $u_n =\sum_{i=1}^n u_{n-i}a_i$</p> <p>It is easy to prove that there exists some positive term $\lambda$ such that $(u_n)$ growth faster than $(\lambda-\epsilon)^n$ and slower than $(\lambda+\epsilon)^n$ for any $\epsilon>0$. I would like to know if it is possible to get better bounds, even by adding if necessary some hypothesis on the coefficients $(a_i)$ (but of course this should not be a periodic sequence, otherwise this is well known and too easy).</p> <p>Thanks by advance for your comments !</p> http://mathoverflow.net/questions/62394/asymptotic-behaviour-of-a-sequence/62422#62422 Answer by Aaron Meyerowitz for Asymptotic behaviour of a sequence Aaron Meyerowitz 2011-04-20T15:24:52Z 2011-04-26T08:03:05Z <p>Let me slightly change the notation. You have some sequence $\mathbf{a}=a_0,a_1,\cdots$ with each $a_i$ either $0$ or $1$. Define a sequence $u_0,u_1,u_2,\cdots$ by setting $u_m=0$ for $m \lt 0$, $u_0=1$ and for any $n \ge 0$, $u_{n+1}=\sum_{i=1}^{\infty}a_iu_{n-i}.$ As you note in a comment, if $a_1=1$ then $u_i$ is a non-decreasing and eventually increasing sequence (excluding a trivial case). The sequence $u_i$ will eventually be increasing as long as the set of $j$ with $a_j=1$ has a $\gcd$ of $1$.</p> <p>Consider the power series $f(r)=r-(a_0+\frac{a_1}{r}+\frac{a_2}{r^2}+\cdots).$ Then $f(r)$ is defined and increasing for $r \gt 1.$ There is a unique $\lambda=\lambda_{\mathbf{a}}>1$ with $f(\lambda)=0.$ I think that there should be a constant $c \le 1$ with $\lim \frac{a_n}{c\lambda^n}=1$. We can also say that $\lambda \le 2$ with equality only in the degenerate case that $a_i=1$ for all $i$. For any $1 \lt r \lt 2$ we can create an $\mathbf{a}$ with $\lambda_{\mathbf{a}}=r$ by simply choosing the $a_i$ one at a time to keep the (non-decreasing) partial sums of $f(r)$ non-negative.</p> <p>We can partially order the possible sequences $\mathbf{a}=(a_i)$ by saying <code>$\mathbf{a}&lt;\mathbf{b}$</code> when $a_i=b_i$ for $0 \le i \lt j$ and <code>$0=a_j&lt;b_j=1.$</code> In this case, <code>$\lambda{\mathbf{a}}&lt;\lambda_{\mathbf{b}}$.</code></p> <p>In case $a_i=0$ from some point on we know how to find $\lambda$ as the root of a polynomial and if $a_i=1$ from some point on we again know how to find $\lambda$ as the root of a polynomial (perhaps with a coefficient equal to $2$.So this gives us both a lower bound and an upper bound on $\lambda_{\mathbf{a}}$ based on any initial portion of $\mathbf{a}.$ </p> <p>I'll stop there for now although probably more can be said.</p> <p>Consider the $2^d$ sequences $\mathbf{a}$ with $a_{d+m}=0$ for $m \gt 0.$ If all the roots, real and complex , of $f(r)$ are plotted then you should get a picture <em>something</em> like the one below. This plot is for $d=12$ you can see a similar one at <a href="http://mathoverflow.net/questions/24136" rel="nofollow">this question</a> </p> <p><img src="http://img140.imageshack.us/img140/3160/polroots.jpg" alt="alt text"> . </p>