2
$\begingroup$

I've learned a lot about the power of generating functions, and it seems to me that a lot of combinatorial identities that are normally solved with combinatorial techniques are readily solved by generating functions. And I think this is true in almost all of the cases I've seen. While I've definitely ran into problems that I couldn't solve using generating functions alone, I've looked a bit into more advanced generating function techniques, and I know that there is a lot of genfunc skills that I do not know. In particular the methods of PIE and DIE come to mind as techniques that are not readily solveable by generating functions. But even with my knowledge, I have been able to solve some classic P/DIE identities using generating functions. So I was wondering whether generating functions are the ultimate tool in regards to combinatorial identities?

But even then, I also recall that there are some identities that while I couldn't figure out a solution using generating functions, the given proof was purely algebraic. So then I also ask, are generating functions and other purely (up to interpretation what this entails) algebraic methods an ultimate toolkit for combinatorial identities? Or do we still need to think about combinatorial interpretations of expressions? Just to clarify, I'm looking for combinatorial identity problems that can't be solved by generating functions.

$\endgroup$
4
  • $\begingroup$ Among the techniques for working with combinatorial identities, summation by parts should be in every mathematician's toolkit. $\endgroup$
    – P. Lawrence
    Commented Mar 14, 2023 at 3:26
  • $\begingroup$ Do you have examples of using summation by parts in a combinatorial identity? I haven't used that outside of analysis lol $\endgroup$
    – Alan Abraham
    Commented Mar 14, 2023 at 3:29
  • $\begingroup$ ‘[A]re generating functions and other purely […] algebraic methods an ultimate toolkit for combinatorial identities?’ Is the hammer in your toolbox the only tool you’ll need? $\endgroup$
    – A rural reader
    Commented Mar 16, 2023 at 2:42
  • $\begingroup$ No I guess not, but I would like an explanation for why such an analogy applies here... $\endgroup$
    – Alan Abraham
    Commented Mar 16, 2023 at 20:55

1 Answer 1

Reset to default
1
$\begingroup$

For combinatorial identities, there are general methods using hypergeometric series (see Gosper Wilf and Zeilberger). And generating function is powerful, especially with Lagrange inversion formula.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .