most recent 30 from http://mathoverflow.net 2013-06-20T05:54:15Z http://mathoverflow.net/feeds/question/15238 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15238/how-to-estimate-the-growth-of-a-recurrence-sequence mr.gondolier 2010-02-14T06:56:35Z 2010-02-14T23:26:40Z

<p>If we have a linear recurrence sequence where each term depends on all previous terms, say</p> <p>$a_n = \sum_{k=0}^{n-1} \binom{n}{k} a_k, \quad a_0 = 1$</p> <p>is there any way to estimate the growth of a_n in terms of a Big-O notation?</p> <p>I suppose the growth must be super-exponential, because if $a_1, \ldots, a_{n-1}$ grows exponentially, say, $q^i$, then we have $a_n = (q+1)^n - q^n$. Hence The exponent grows from $q$ to $q+1$. But I am not sure if this serves as an argument.</p> <p>Thanks!</p>

http://mathoverflow.net/questions/15238/how-to-estimate-the-growth-of-a-recurrence-sequence/15239#15239 Qiaochu Yuan 2010-02-14T07:09:00Z 2010-02-14T07:09:00Z

<p>A very powerful way to estimate the growth of a recurrence is to look at the analytic properties of the generating function that it implies. In this case we should take the exponential generating function $f(x) = \sum_{n \ge 0} \frac{a_n}{n!} x^n$, giving the identity</p> <p>$$2f(x) = e^x f(x) + 1$$</p> <p>hence $f(x) = \frac{1}{2 - e^x}$ (one can also deduce this by a purely combinatorial argument). This function is meromorphic, so the growth rate of $a_n$ is dictated by the position of its poles. The pole closest to the origin is at $x = \ln 2$, which gives $a_n \sim \frac{n!}{(\ln 2)^n}$. The other poles contribute similar terms.</p> <p>The wonderful thing about this technique is that it can work <strong>even if you can't solve for the generating function</strong> because recurrences that imply certain types of identities for the generating function can still control its analytic properties. The best reference I know for this kind of stuff is Flajolet and Sedgewick's <em>Analytic Combinatorics</em>, which is available free online.</p>

http://mathoverflow.net/questions/15238/how-to-estimate-the-growth-of-a-recurrence-sequence/15245#15245 Ross Snider 2010-02-14T08:38:41Z 2010-02-14T08:38:41Z

<p>I believe you can create two new recurrence sequences each of whose generating function is known which bound the sequence in question tightly. That gives a really good idea of the growth.</p>

http://mathoverflow.net/questions/15238/how-to-estimate-the-growth-of-a-recurrence-sequence/15293#15293 Gerry Myerson 2010-02-14T23:26:40Z 2010-02-14T23:26:40Z

<p>This is sequence A000670 in the On-Line Encyclopedia of Integer Sequences. There are many comments, formulas, links, and references there. </p>