Talk:Generating function

Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

[[Geometric_series#Closed-form_formula|geometric series]] The anchor (#Closed-form_formula) has been deleted by other users before.

Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

References please

Please give the references for the very nice formulas in the section on asymptotics of coefficients. Asympt (talk) 18:57, 21 November 2021 (UTC)[reply]

I find a paper that uses a formula quite like this and cites G. Pólya and G. Szegő, Problems and Theorems in Analysis, Vol 1. (1972), Exercise 174. And I see a citation to Wilf generatingfunctionology (1994), sections 5.2 and 5.3. If you wanted to check those and insert any that are applicable, that'd be great! —

Q

uantling (talk | contribs) 22:56, 21 November 2021 (UTC)[reply]

Ancient comment

The information here is really not enough... it didn't give me any idea how to calculate the generating function coefficients. It's algebra and series, but the article should list the most used tricks: binomial theorem, infinite geometric series, convolution products, etc. -Iopq 19:59, 18 October 2005 (UTC)[reply]

Definition

I am not an expert on the field, so I will not dare to introduce the following definition myself. But if somebody does agree, please include under "Definitions" the following:

"A generation function is a transformation that converts a given sequence, S = {a_n}, into a continous function, f(x), through a series expantion whose coeficients are the elements a_n of the sequence S."

or something similar you find more appropiate.

Well, I don't think that's very clear. The powers of a variable are really place-olders, here. There is no necessary connection to continuity. Charles Matthews 12:19, 16 November 2005 (UTC)[reply]

I agree. Many useful generating functions are not continuous or even convergent. Any definition must stress the formal nature of the series. --Zero 22:52, 16 November 2005 (UTC)[reply]

Absolutely. (No pun intended.) To call these things "continuous" is absurd. Michael Hardy 20:13, 17 November 2005 (UTC)[reply]

Very old thread, but I don't agree. A huge number of interesting generating functions are meromorphic. The main heuristic motivation for using exponential generating functions is often that the coefficients grow too quickly for an ordinary generating function to converge. Off the top of my head I can't think of a single practically useful univariate generating function that has bad analytic properties. By "practically useful", I mean something like "can be found printed in a paper or book". Obviously any precise definition will say almost no sequences of reals have convergent generating functions, but that's just not interesting. The multivariate case is another story, particularly with infinitely many variables, but that's not what the person was talking about.2607:F720:F00:4834:E985:5B77:A9AF:D672 (talk) 14:45, 15 May 2019 (UTC)[reply]

Indeed, it is very, very old. But as long as it is being revived: you are wrong about both the heuristic and the substance. The "right" heuristic for exponential generating functions is about labelings, and here is a practically useful (in your definition) use of generating functions with bad analytic properties (lazily drawn from my own work because only one example is necessary to make the point). See also EC1, notes on Chapter 1. --JBL (talk) 15:20, 15 May 2019 (UTC)[reply]

I said the growth rate is "often" the main heuristic. It's certainly not the only one. I also did not say there are no "useful" univariate generating functions with bad analytic properties, though I like the examples in your paper, like

\Psi (x)

and friends. My point was to respond to `To call these things "continuous" is absurd', when it's frequently not, especially in the context of an introduction to the subject. 2607:F720:F00:4834:E985:5B77:A9AF:D672 (talk) 15:54, 15 May 2019 (UTC)[reply]

I just noticed that the german version is not liked here it's called "Erzeugende Funktionen", url is here: http://de.wikipedia.org/wiki/Erzeugende_Funktion — Preceding unsigned comment added by 80.254.173.61 (talk) 16:44, 18 December 2005 (UTC)[reply]

Examples please!

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. For example,... (a nice easy example or two, please!)

This article is fairly typical of current Wikipedia mathematics articles: it dives headlong into a mass of detail without first explaining the basics. This is supposed to be an online encyclopedia, not a maths textbook!

Education is a process of diminishing deception. Start off with the simple stuff; the ifs and buts come later.

--84.9.78.198 14:14, 27 November 2006 (UTC)[reply]

If you read on past the Definitions section you will find an Examples section with four examples of different types of generating function for the sequence of square numbers, and also an extended example showing how the ordinary generating function for the Fibonacci numbers is derived. If Examples came before Definitions the article would be more difficult to follow, as you would not know what the Examples were meant to be illustrating. Gandalf61 14:41, 27 November 2006 (UTC)[reply]

Uniqueness of F

I made a change to the article, dropping a condition (something being an integral domain) on the explanation of the uniqueness of the inverse of (1-X). If F is any ring with a unit, not necessarily commutative or an integral domain, then the only power series $f(X)\in F[[X]]$ such that $1=(1-X)f(X)$ is $f(X)=1+X+X^{2}+\dots$ . To see this, let $f(X)=f_{0}+f_{1}X+f_{2}X^{2}+\dots$ . Then $(1-X)f(X)=f_{0}+(f_{1}-f_{0})X+(f_{2}-f_{1})X^{2}+...$ . Solving $1=(1-X)f(X)$ means that $f_{0}=1,(f_{1}-f_{0})=0,(f_{2}-f_{0})=0,\dots$ and therefore $1=f_{0}=f_{1}=f_{2}=\dots$ . The only multiplication in the ring F is used in this proof is multiplication by 1 and -1 in F. Therefore neither general commutativity of the ring F nor F being an integral domain is required. Indeed multiplication in F need not even be associative. (So, the result holds if F is the octonions, for example.) It is only required that multiplication in F have an identity element 1. Multiplication by -1, and its necessary properties, is then implied by F being a ring. Of course, multiplication by X in $F[[X]]$ has been used, and commutativity of this operation , that is, $Xa=aX$ has been used, as has the fact if $Xa=0$ then $a=0$ . In general, though if the ring of coefficient is not an integral domain or commutative, then neither is the resulting power series ring. —Preceding unsigned comment added by DRLB (talk • contribs) 15:26, 17 October 2008 (UTC)[reply]

That's a nice extension of the given statement. All the article actually uses is that formal power series with coefficients in any ring form a ring -- two-sided inverses are unique in any ring. --Charleyc (talk) 16:23, 18 October 2008 (UTC)[reply]

Good point about uniqueness of two-sided inverses, probably worth saying in the article. Instead of saying this is unique, say this is a two-sided inverse, and thus it is unique. (I'm not sure if two-sided inverses are unique in non-associative rings, but I think that's out-of-scope for the article.) DRLB (talk) 14:50, 20 October 2008 (UTC)[reply]

Formulae

I noticed that all summation formulae on the page look like this: for each natural n sum a_i*x^n or something. I believe this should be fixed, because 1/(1-x) is not x+x^2+x^3+... but 1+x+x^2+x^3... —Preceding unsigned comment added by 85.187.35.160 (talk) 13:47, 20 August 2009 (UTC)[reply]

Fixed - I have replaced

\sum _{n\in \mathbf {N} }

with

\sum _{n=0}^{\infty }

, which was clearly what was intended in each case. Gandalf61 (talk) 15:55, 20 August 2009 (UTC)[reply]

"Generating series" terminology

The current version of the article indicates that "generating series" is "more correct" than "generating function." While I agree that generating functions aren't really functions (for instance, because their evaluation at specific points isn't what they're about), I worry that they aren't really series either (for instance, because whether or not they converge isn't what they're about). Given that there is now a citation (which I haven't checked!) to show that "generating series" is also in use, might we simply say that it is an "alternative" rather than "more correct"? Quantling (talk) 16:00, 27 May 2010 (UTC)[reply]

The "series" in "generating series" refers to formal power series, where convergence is not much of an issue either (the term "generating formal power series" would be a bit heavy). Series are not necessarily about convergence, so I don't think this is much of a problem. Marc van Leeuwen (talk) 10:35, 28 May 2010 (UTC)[reply]

Is this a generating function?

 $\pi (\cot(\pi (c+z))-2\cot(2\pi (c-z))-2\cot(2\pi (c+z))+\cot(\pi (c-z)))=-2\left(\sum _{k=0}^{\infty }z^{2k}\sum _{x=1}^{\infty }{\frac {1}{(x+c-1/2)^{2k+1}}}-{\frac {1}{(x-c-1/2)^{2k+1}}}\right)$

taking multiple derivatives with respect to z closed form sums can be obtained such as:

 $\pi ^{3}(8(\cot(2c\pi )+\cot ^{3}(2c\pi ))-(\cot(c\pi )+\cot ^{3}(c\pi )))=\sum _{x=1}^{\infty }{\frac {1}{(x+c-1/2)^{3}}}-{\frac {1}{(x-c-1/2)^{3}}}$

$=-{\frac {\pi ^{3}\sin(c\pi )}{\cos ^{3}(c\pi )}}$

$\cot(\pi (c+z))\approx \cot(c\pi )-z\pi (1+\cot ^{2}(c\pi ))+z^{2}\pi ^{2}(\cot(c\pi )+\cot ^{3}(c\pi ))$

http://iamned.com/math —Preceding unsigned comment added by 67.161.40.148 (talk) 11:02, 30 June 2010 (UTC)[reply]

confusing definition

The first sentence of the introduction says a generating function is "an infinite sequence of numbers". The second sentence says it is a single number, namely: "the sum of this infinite series". Apart from the morph of "sequence" into "series", this is pretty confusing. RobLandau (talk) 07:40, 8 February 2018 (UTC)[reply]

@RobLandau: Generating functions are not sequences. The article does not say that; the article says they are used to describe sequences. I see no confusion here.--Jasper Deng (talk) 07:44, 8 February 2018 (UTC)[reply]

The first sentence was not very clearly written, I have tried to rephrase it (in keeping also with the general rule that encyclopedia articles are about things, not about names for things). --JBL (talk) 13:05, 8 February 2018 (UTC)[reply]

Two of us, RobLandau and myself, have now pointed out that the status quo ante of this sentence, which @Joel B. Lewis: has twice restored, doesn’t make sense. The original and restored sentence The sum of this infinite series is the generating function, as I said in my edit summary when I changed it and as RobLandau said above, is certain to give some people the impression that it means “The number that this series sums to is the generating function”, which is not right.

My replacement sentence, which I’m not wedded to, said The summation of this infinite series is the generating function. Here summation, as per its article, means the addition of a sequence of numbers, which correctly refers to the entity rather than the result.

Joel restored the original with the edit summary The sum (that is, the whole infinite series) is the GF. "Summation" does not make sense here.) But many readers will not understand that here sum is intended to mean the whole infinite series. Please be open to making an improvement given that the inadequacy of the current version has been pointed out by more than one person. I.e., please come up with a version that is better than both sum and summation. Thanks! Loraof (talk) 16:16, 29 May 2018 (UTC)[reply]

I would avoid the use of either "sum" or "summation" in this setting. I agree with Joel's objection to using "summation" and I am also not happy with the original phrasing. I would suggest using, This formal power series is the generating function. --Bill Cherowitzo (talk) 17:04, 29 May 2018 (UTC)[reply]

Loraof, I do not think your description of my actions is accurate: the unique edit I made in response to RobLandau's comments here is this one, which did not "restore" anything. The phrase "the summation of a series" makes no sense; if it did make sense, it would mean exactly the same as "the sum of the series". Indeed, the series is the sum; this sum is not a [real or complex] number because the individual summands are not [real or complex] numbers. I think Bill's suggestion is a completely acceptable alternative for that sentence. The immediately following sentence leaves something to be desired, as well. --JBL (talk) 18:10, 29 May 2018 (UTC)[reply]

Your action that I was referring to was your revert of my edit at 11:48 today, which restored what I had altered, and not your earlier edit on 8 February. Loraof (talk) 19:31, 29 May 2018 (UTC)[reply]

Your comment describes me has having "twice restored" something. --JBL (talk) 19:35, 29 May 2018 (UTC)[reply]

Ah, sorry about that. On the first one I should have said that you kept it while changing the adjacent sentence after RobLandau flagged the wording of both sentences. Sorry. Loraof (talk) 20:38, 29 May 2018 (UTC)[reply]

Function* listed at Redirects for discussion

An editor has asked for a discussion to address the redirect Function*. Please participate in the redirect discussion if you wish to do so. Jasper Deng (talk) 07:51, 11 May 2019 (UTC)[reply]

Article is a mess

This article has so many issues. I'll list the biggest ones in the hope that (perhaps over years) they'll eventually get fixed.

By far the biggest issue: the material on OGF's and EGF's needs to be split into its own articles. This article should be a panoramic view of generating functions with tons of links to specific instances (as is already done for Lambert, Bell, and formal Dirichlet series). The current version is trying to do way too much at once and mainly succeeds in doing many things badly. The length is probably dissuading people from wanting to jump in and help clean up as well.
The writing frequently feels inappropriate for an encyclopedia. It's often clearly trying to teach the reader from the ground up rather than summarize the topic, like in "Example 3: Generating functions for mutually recursive sequences". Consequently it's often long-winded with frequent asides and some irrelevant bits, like "We suggest an approach by generating functions." Every word should be carefully weighed to decide if it's worth saying, which by no means has been done.
There are tons of "local" issues, like the fact that none of the "precise, technical" definitions actually reference base rings or power series, the large number of lengthy equations that should be displayed rather than in-line, the ad-hoc, inconsistent use of theorem-like "environments".... 2607:F720:F00:4834:E985:5B77:A9AF:D672 (talk) 15:31, 15 May 2019 (UTC)[reply]

must it be infinite?

Recently someone asked for the probability distribution of the sum of 64 rolls of a biased die, and I replied by expanding the polynomial $({\frac {2}{5}}x^{1}+{\frac {1}{5}}x^{2}+{\frac {1}{5}}x^{3}+{\frac {1}{5}}x^{4})^{64}$ . Is that not a generating function because it's not infinite? —Tamfang (talk) 14:56, 16 October 2019 (UTC)[reply]

Finite sequences embed into infinite sequences in a natural way, by appending all 0s. So, for example, the sequence of coefficients of the series you mention can be understood to be (0, 0, ..., 0, (2/5)^64, ..., 1/5^64, 0, 0, 0, ...). The emphasis on "infinite" in the lead is slightly misplaced. --JBL (talk) 18:17, 16 October 2019 (UTC)[reply]

The wiki-linking in the lede is also rather submarine. It links to formal power series with the text "power series", then drops in the phrase "formal power series" without explaining what "formal" means in this context, then links to formal power series again with the text "formal series". Next we get Generating functions were first introduced by Abraham de Moivre in 1730 — fine — in order to solve the general linear recurrence problem. Wait, what's that? Nor does the rest of the article really make clear what "the general linear recurrence problem" is. It talks about finding a closed-form solution given a recurrence relation, and about extracting a recurrence relation given a generating function. Is "the" general linear recurrence problem just the challenge of understanding linear recurrences in general? XOR'easter (talk) 05:21, 17 October 2019 (UTC)[reply]

Formula for generating function for a linear recursive sequrnce.

The following formula is really easy to use. Shall it be included in this article?

Let $s_{n}$ be a linear recursive sequence of order k with initial conditions $\{s_{0},s_{1},\ldots ,s_{k-1}\}$ and recursive relation $s_{n}=\sum _{i=1}^{k}a_{i}s_{n-i}.$

Then the generating function for $s_n$ is given by the formula

$(\sum _{i=0}^{k-1}(\sum _{j=0}^{i}(-a_{j})*s_{i-j})*x^{i-k})/f(x^{-1})$ — Preceding unsigned comment added by Kaiwang45 (talk • contribs) 15:49, 27 July 2020 (UTC)[reply]

Blackboard bold formatting

@Quantling: Greetings! Regarding this revert...the use of <math>...</math> is required by MOS:BBB. If we want the nearby markup to be consistent, that's fine; we would just need to convert it to also use <math>...</math>. -- Beland (talk) 16:21, 27 March 2023 (UTC)[reply]

@Beland: Good point. To be more consistent with MOS:STYLERET, other possibilities are to use

In this section we give formulas for generating functions enumerating the sequence ${f an + b}$ given an ordinary generating function $F (z)$ , where $a, b \in N$ , $a \geq 2$ , and $0 \leq b < a$ .
In this section we give formulas for generating functions enumerating the sequence ${f an + b}$ given an ordinary generating function $F (z)$ , where $a \geq 2$ and $0 \leq b < a$ are integers.

What do you think? —

Q

uantling (talk | contribs) 17:39, 27 March 2023 (UTC)[reply]

@Quantling: "

a

and

b

are integers" is certainly a lot less jargony than using the blackboard bold notation. -- Beland (talk) 17:45, 27 March 2023 (UTC)[reply]

I made an edit to the article. If that's not right somehow, please fix or revert it, and/or continue the discussion here. Thank you —

Q

uantling (talk | contribs) 17:55, 27 March 2023 (UTC)[reply]

Done; thanks for your help ironing this out! -- Beland (talk) 22:09, 27 March 2023 (UTC)[reply]

Remove Sections

It seems to be a complaint that the article is too huge to read. I was wondering if we can cut some sections down. Obviously there must have been those before me who wondered, so I mean to ask: What's a systematic way to maintain such a list?

For starters, we should probably remove P-holonomic functions and J-fractions and give them their dedicated pages. But beyond that, at the time of writing this, I am not sure of what optimisations one can perform.

Additionally, I am a bit biased towards the content in the wiki and it is hard for me to point out precise areas which might prove to be educationally ill-formed to most. So I would like some feedback in that direction, thank you! (Ex: The 'Article is a mess' post above seems rather insightful, and I'll try to propose concrete edits which might circumvent the proposed issues.)

Also, how about this one: We just list a couple applications of generating functions (I honestly think snake oil or something is a good enough thing to convince people that they're 'useful', and then maintain a 'main article' on applications). I wish to scrap off the entire J-fraction part, write something about them in a main link, write about transforming between ordinary and exponential generating functions and then remove the whole transforming part.

Yeetcode (talk) 03:27, 25 November 2023 (UTC)[reply]

In hindsight, the applications part can be cut down here and there. However, it's the ordinary generating functions part that needs to basically go out of the window. It's WAY too extensive. Yeetcode (talk) 06:26, 16 February 2024 (UTC)[reply]

Spreading the content to multiple articles that specialize in specific aspects sounds good to me. However, much of the content is quite interesting to me, so I am hoping that, as it leaves this article, it does go somewhere, not merely to the null device. —

Q

uantling (talk | contribs) 13:54, 16 February 2024 (UTC)[reply]

We could start by checking that all the content on ordinary generating functions makes it to an ordinary generating functions wiki, and then we can prune most of the content from here. Yeetcode (talk) 13:55, 19 February 2024 (UTC)[reply]