Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See herehere for a more involved, less mechanic example.
Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.
Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.
One can employ complex analysis machinery, specifically singularity analysis, in order to obtain asymptotics for the coefficients; buzzwords include Darboux's method and saddle-point method. These are based on the residue theorem and Cauchy's integral formula. See [5][6] for details.
- You can do similar things with exponential, Dirichlet and some other generating functions. Which works best depends on the sequence at hand and in particular whether you find the necessary closed forms.
- For example from the TCS Cheat Sheet or [3].
- generatingfunctionology by H. Wilf (1994, 2nd ed.) -- available for free download
- Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik (1994, 2nd ed.)
- Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd edition, 2013) -- available for free download
- Analytic Combinatorics by RP. Flajolet and R. Sedgewick (2009) -- available for free download
One can employ complex analysis machinery, specifically singularity analysis, in order to obtain asymptotics for the coefficients; buzzwords include Darboux's method and saddle-point method. These are based on the residue theorem and Cauchy's integral formula. See [5] for details.
- You can do similar things with exponential, Dirichlet and some other generating functions. Which works best depends on the sequence at hand and in particular whether you find the necessary closed forms.
- For example from the TCS Cheat Sheet or [3].
- generatingfunctionology by H. Wilf (1994, 2nd ed.) -- available for free download
- Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik (1994, 2nd ed.)
- Analytic Combinatorics by R. Flajolet and R. Sedgewick (2009) -- available for free download
One can employ complex analysis machinery, specifically singularity analysis, in order to obtain asymptotics for the coefficients; buzzwords include Darboux's method and saddle-point method. These are based on the residue theorem and Cauchy's integral formula. See [6] for details.
- You can do similar things with exponential, Dirichlet and some other generating functions. Which works best depends on the sequence at hand and in particular whether you find the necessary closed forms.
- For example from the TCS Cheat Sheet or [3].
- generatingfunctionology by H. Wilf (1994, 2nd ed.) -- available for free download
- Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik (1994, 2nd ed.)
- Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd edition, 2013) -- available for free download
- Analytic Combinatorics by P. Flajolet and R. Sedgewick (2009) -- available for free download
Every series of natural numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.
Let $(a_n)_{n\in\nats}$ a series of natural numbers. Then, the formal power series
for some fixed $b_1, \dots, b_k \in \nats$$b_1, \dots, b_k \in \mathbb{R}$ and $f(n) : \nats \to \nats$ a function independent of all $a_i$. Now we simply insert both anchors and recursive part into the ansatz, that is
Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.
Also note that the general techniques also work if the objects sought are complex numbers, or even polynomials.
Every series of natural numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.
Let $(a_n)_{n\in\nats}$ a series of natural numbers. Then, the formal power series
for some fixed $b_1, \dots, b_k \in \nats$ and $f(n) : \nats \to \nats$ a function independent of all $a_i$. Now we simply insert both anchors and recursive part into the ansatz, that is
Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.
Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.
Let $(a_n)_{n\in\nats}$ a series of numbers. Then, the formal power series
for some fixed $b_1, \dots, b_k \in \mathbb{R}$ and $f(n) : \nats \to \nats$ a function independent of all $a_i$. Now we simply insert both anchors and recursive part into the ansatz, that is
Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.
Also note that the general techniques also work if the objects sought are complex numbers, or even polynomials.
