2
$\begingroup$

I teach generating functions as part of my Discrete Mathematics course for undergraduate Computer Science students. Over the years, I have experimented with different approaches to introduce this topic. My current approach involves:

  1. Explaining that generating functions are not actually functions in the traditional sense.
  2. Defining operations like addition and multiplication for generating functions.
  3. Discussing why we use closed forms like $-\log(1-x)$ to perform arithmetic on generating functions, despite the divergence concerns.

However, students often appear confused. This semester, I devoted a full 75-minute lecture to these foundational aspects, but the response was still subdued compared to lessons on more concrete topics.

My Question: Would it be more effective to de-emphasise the rigorous mathematical foundations of generating functions and instead focus on their application to solve combinatorial problems? (I do have the authority to make minor adjustment to the syllabus like this.)

I am particularly interested in hearing from educators who have faced similar dilemmas. What strategies have worked for you in balancing the abstract mathematical theory with practical applications, especially for students whose primary focus is not pure mathematics?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Hmmm.... Do you really have many interesting applications where the radius of convergence is $0$? $\endgroup$
    – fedja
    Commented Sep 11 at 4:10
  • $\begingroup$ Not really. But it's sort of standard thing in generating function textbooks to start by rigorously define them as formal power series. It feels a bit too hand-waving to drop them. $\endgroup$
    – LeafGlowPath
    Commented Sep 11 at 5:16
  • 1
    $\begingroup$ Then just define them for the purposes of the course as power series with positive radius of convergence, enjoy all benefits of the theory of analytic functions in a disk, derive all formulas under this assumption, and just tell the students that "for some counting problems, the general method will result in a divergent series, in which case one will have to treat it in abstract algebraic rather than complex analytic way, but most computations will be pretty much the same" and stop there. There is nothing non-rigorous in that. You'll just restrict the applicability of the idea a bit. $\endgroup$
    – fedja
    Commented Sep 11 at 9:58
  • 3
    $\begingroup$ @fedja Aren't there tons of examples? e.g. most objects that are counted with labels. Now, for these you can usually pass to exponential generating functions and get a positive radius of convergence, but still. $\endgroup$
    – Adam
    Commented Sep 11 at 13:20
  • $\begingroup$ @Adam You are right. That's why I asked my first question above ;-) $\endgroup$
    – fedja
    Commented Sep 11 at 18:32

1 Answer 1

Reset to default
4
$\begingroup$

Since you are in a CS department, I think you're better off convincing students by examples that the whole machinery works. Then just say things really can be made more rigorous with some technical math, but that is not the point of your course.

While it is too sophisticated to present to CS undergrads or to put in most combinatorics books, by viewing formal power series with coefficients in $\mathbf C$ as the $x$-adic completion $\mathbf C[[x]]$ of the polynomial ring $\mathbf C[x]$, the "divergence" issue with $-\log(1-x)$ disappears: at all $g(x)$ in $1 + x\mathbf C[[x]]$, $\log(g(x)) = \sum_{n \geq 1} (-1)^{n-1}g(x)^n/n$ converges and it lies in $x\mathbf C[[x]]$.

I personally find this completion approach to formal power series much more satisfying than the coefficient-by-coefficient reasoning traditionally used to justify computations with formal power series, esp. when you need to explain anything involving composition of formal power series. By using a completion perspective we gain access to topological language, and in particular arguments by continuity.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For proving identities, it is a great point of view. For finding asymptotics, I'm not so sure... But there are only two things in the entire Universe that are perfect in all respects: God and Mary Poppins, and at least one of them is a fictional character :-) $\endgroup$
    – fedja
    Commented Sep 11 at 10:05
  • 1
    $\begingroup$ @fedja sure, for asymptotics you want the complex-analytic point of view. By “computations” I only had in mind ones like ordinary algebra but also differentiation, composition, and inversion that apply to fairly general formal power series, thereby not requiring you to limit attention to series with positive radius of convergence in the complex numbers. $\endgroup$
    – KCd
    Commented Sep 11 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.