Editing Generating function (section)

=== Asymptotic growth of a sequence ===
In calculus, often the growth rate of the coefficients of a power series can be used to deduce a [[radius of convergence]] for the power series. The reverse can also hold; often the radius of convergence for a generating function can be used to deduce the [[Asymptotic analysis|asymptotic growth]] of the underlying sequence.

For instance, if an ordinary generating function {{math|''G''(''a''<sub>''n''</sub>; ''x'')}} that has a finite radius of convergence of {{mvar|r}} can be written as
<math display="block">G(a_n; x) = \frac{A(x) + B(x) \left (1- \frac{x}{r} \right )^{-\beta}}{x^\alpha}</math>

where each of {{math|''A''(''x'')}} and {{math|''B''(''x'')}} is a function that is [[analytic function|analytic]] to a radius of convergence greater than {{mvar|r}} (or is [[Entire function|entire]]), and where {{math|''B''(''r'') ≠ 0}} then
<math display="block">a_n \sim \frac{B(r)}{r^\alpha \Gamma(\beta)} \, n^{\beta-1}\left(\frac{1}{r}\right)^n \sim \frac{B(r)}{r^{\alpha}} \binom{n+\beta-1}{n}\left(\frac{1}{r}\right)^n = \frac{B(r)}{r^\alpha} \left(\!\!\binom{\beta}{n}\!\!\right)\left(\frac{1}{r}\right)^n\,,</math>
using the [[gamma function]], a [[binomial coefficient]], or a [[multiset coefficient]].  Note that limit as {{mvar|n}} goes to infinity of the ratio of {{math|''a''{{sub|''n''}}}} to any of these expressions is guaranteed to be 1; not merely that {{math|''a''{{sub|''n''}}}} is proportional to them.

Often this approach can be iterated to generate several terms in an asymptotic series for {{math|''a''<sub>''n''</sub>}}. In particular,
<math display="block">G\left(a_n - \frac{B(r)}{r^\alpha} \binom{n+\beta-1}{n}\left(\frac{1}{r}\right)^n; x \right) = G(a_n; x) - \frac{B(r)}{r^\alpha} \left(1 - \frac{x}{r}\right)^{-\beta}\,.</math>

The asymptotic growth of the coefficients of this generating function can then be sought via the finding of {{mvar|A}}, {{mvar|B}}, {{mvar|α}}, {{mvar|β}}, and {{mvar|r}} to describe the generating function, as above.

Similar asymptotic analysis is possible for exponential generating functions; with an exponential generating function, it is {{math|{{sfrac|''a''<sub>''n''</sub>|''n''!}}}} that grows according to these asymptotic formulae. Generally, if the generating function of one sequence minus the generating function of a second sequence has a radius of convergence that is larger than the radius of convergence of the individual generating functions then the two sequences have the same asymptotic growth.

==== Asymptotic growth of the sequence of squares ====
As derived above, the ordinary generating function for the sequence of squares is:
<math display="block">G(n^2; x) = \frac{x(x+1)}{(1-x)^3}.</math>

With {{math|1=''r'' = 1}}, {{math|1=''α'' = −1}}, {{math|1=''β'' = 3}}, {{math|1=''A''(''x'') = 0}}, and {{math|1=''B''(''x'') = ''x'' + 1}}, we can verify that the squares grow as expected, like the squares:
<math display="block">a_n \sim \frac{B(r)}{r^\alpha \Gamma(\beta)} \, n^{\beta-1} \left (\frac{1}{r} \right)^n = \frac{1+1}{1^{-1}\,\Gamma(3)}\,n^{3-1} \left(\frac1 1\right)^n = n^2.</math>

==== Asymptotic growth of the Catalan numbers ====
{{Main|Catalan number}}

The ordinary generating function for the [[Catalan number]]s is
<math display="block">G(C_n; x) = \frac{1-\sqrt{1-4x}}{2x}.</math>

With {{math|1=''r'' = {{sfrac|1|4}}}}, {{math|1=''α'' = 1}}, {{math|1=''β'' = −{{sfrac|1|2}}}}, {{math|1=''A''(''x'') = {{sfrac|1|2}}}}, and {{math|1=''B''(''x'') = −{{sfrac|1|2}}}}, we can conclude that, for the Catalan numbers:
<math display="block">C_n \sim \frac{B(r)}{r^\alpha \Gamma(\beta)} \, n^{\beta-1} \left(\frac{1}{r} \right)^n = \frac{-\frac12}{\left(\frac14\right)^1 \Gamma\left(-\frac12\right)} \, n^{-\frac12-1} \left(\frac{1}{\,\frac14\,}\right)^n = \frac{4^n}{n^\frac32 \sqrt\pi}.</math>