Why Generating Functions Work in Combinatorics

[samspotting]

Why does generating functions work? In combinatorics we've accepted not to worry about convergence, and we saw how to get a function that returns the nth term of the fibonnaci sequence from the recursive definition, but there was so much magic in that.

The prof said not to worry about it until grad school.

 

[HallsofIvy]

What kind of "generating function" are you talking about? I know several slightly different kinds of "generating functions" but none of them are connected with getting a closed form equation from a recursive equation.

 

[Hurkyl]

Getting the closed form for the Fibonacci sequence seems like a typical application to me... You're thinking about Generating functions, right?

 

[samspotting]

yes indeed.

 

[Edgardo]

Here is an interesting blogpost about generating functions by Foxmath.

 

[samspotting]

Yeah, that is what we covered. It feels too much like calculus, the reasoning behind it all is rather hidden.