5
$\begingroup$

I'm about to introduce the Generating Function concept to a couple of kids. The plan is just to roughly follow Herbert Wilf's Generatingfunctionology's first 12 pages, until Fibonacci numbers and Ch 1.4 "a three term boundary value problem".

I'd like to see an elementary example showing the power of the generating function, something could not be solved (easily) without using it.

Now all examples till Ch 1.4, has solutions without generating function. For example,

  • Example in Ch 1.1, $a_{n+1} = 2a_n+1$, can be solved by introducing $b_n := a_n+1$, such that $b_{n+1}=2b_n$
  • Example in Ch 1.2, $a_{n+1} = 2a_n+n$, can be solved by introducing $b_n := a_n + n + 1$, after which the original relationship has been transformed to $b_{n+1} = 2b_n$.
  • Example in Ch 1.3, the Fibonacci recurrence $F_{n+1} = F_n + F_{n-1}$, can be solved after introducing $r_\pm = (1\pm \sqrt{5})/2$, $G_n := F_{n+1} - r_+ F_n$ and $H_n := F_{n+1} - r_- F_n$, as now we have $G_{n+1} = r_- G_n$ and $H_{n+1} = r_+ H_n$, so one could guess $F_n = c_1 G_n + c_2 H_n$, where $G_n = G_0 r_-^n$, $H_n = H_0 r_+^n$.

In short, all such "elementary solutions", are trying to convert a complex recurrence relation to a simpler one to solve it; while the generating function approach, is taking the whole (infinite) series as one object and analyze the relationships among itself.

Take the Fibonacci recurrence $$F_{n+1} = F_n + F_{n-1}$$ as an example. After defining the generating function $$F(x) := \sum_{n\ge 0} F_n x^n$$the recurrence relationship becomes $$\frac{F(x)-x}{x} = F(x) + xF(x)$$ and then $F(x)$ is solved, based on which $F_n$ can be derived.

This is somewhat like the Fourier transform, to convert issues in time domain to frequency domain to solve it.

Could you please give me some elementary examples (e.g. only one variable case, preferably no prerequisite on calculus), that can be solved by generating function, but are very difficult if not impossible to be solved without using the generating function approach?

$\endgroup$
3
  • 4
    $\begingroup$ What do you mean by "kids"? $\endgroup$
    – Pedro
    Apr 2 at 1:33
  • 1
    $\begingroup$ @Pedro some young people with middle school math knowledge , understanding precalculus but not calculus $\endgroup$
    – athos
    Apr 2 at 5:29
  • 4
    $\begingroup$ I think your sentence "Now all examples till Ch 1.4, has solutions without generating function" is a bit of a red herring. For a lot of things there exists more than one good approach, but they might have different advantages and disadvantages. For instance, your "elementary solution" for the Fibonacci numbers strikes me as not easy at all, because you left out the major step of the solution: one first has to come up with those tranformations and it is not at all clear how to do this. By constrast, generating functions are algorithmic in the sense that one can always use them. $\endgroup$ Apr 4 at 16:19

4 Answers 4

3
$\begingroup$

Chapter 6 of "Applied Combinatorics" by Alan Tucker contains several elementary but powerful examples and exercises of generating functions.

Example 4 asks for the generating function of the number of ways to distribute $r$ identical objects into five distinct boxes with an even number of objects not exceeding 10 in the first two boxes and between three and five in the other boxes.

By inspection, the generating function is

$g(x)=(1+x^2+x^4+x^6+x^8+x^{10})^2(x^3+x^4+x^5)^3$.

It is tedious but instructive to have the students expand this expression into its 27 terms and to notice the coefficients of the powers of $x$. They can then answer the question "In how many ways can 29 identical objects be so distributed?" The answer is 35 ways, which is the coefficient of $x^{29}$.

Then have the students list all 35 ways to check their answer.

$\endgroup$
3
  • $\begingroup$ Why would you have the students list all 35 ways to check their answer? OP mentioned that the students only have an understanding of precalculus (but not calculus), so this would most likely feel very tedious to them. $\endgroup$
    – CrSb0001
    Apr 5 at 0:52
  • 2
    $\begingroup$ Yes, it would be somewhat tedious. That's the point: to show them the power of generating functions rather than brute force. $\endgroup$
    – Mike Z.
    Apr 5 at 0:58
  • $\begingroup$ Ah, I guess I misunderstood what you were trying to say. My bad :) $\endgroup$
    – CrSb0001
    Apr 5 at 0:59
4
$\begingroup$

Why not give the generating function for the Catalan numbers as an example?

For a quick overview:

The Catalan numbers ($C_n$, A000108) is defined as the number of ways that parenthesis can be inserted into the product$$x_0\cdot x_1\cdot...\cdot x_n$$so that the multiplication is still completely specified.

The sequence is as follows (first 10 terms):

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,...

It should be pretty easy to show that$$C_n=\dfrac{{2n}\choose n}{n+1}$$by defining$$c(x)=\sum_{n\ge0}C_nx^n$$$$\implies c(x)=1+xc(x)^2$$(rewriting it as a summary in generalized function form)$$\implies c(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}$$however it must be$$c(x)=\dfrac{1-\sqrt{1-4x}}{2x}$$because we have then that $\lim_{x\to0}c(x)=C_0=1$. If we had chosen the positive branch, then we would have $C_0\ne\lim_{x\to0}c(x)=\infty$.

Now you can expand the function $1-\sqrt{1-4x}$ as a power series using the binomial series$$1-\sqrt{1-4x}=-\sum_{n\ge1}{1/2\choose n}(-4x)^n$$which then can be rewritten as$$-\sum_{n\ge1}\dfrac{(-1)^{n-1}(2n-3)!!}{2^nn!}(-4x)^n\label1\tag1$$which after some simplifying, gives$$1-\sqrt{1-4x}=\sum_{n\ge0}\dfrac2{n+1}{2n\choose n}x^{n+1}$$and dividing by $2x$ on both sides gives$$c(x)=\sum_{n\ge0}C_nx^n=\sum_{n\ge0}\frac{{2n\choose n}}{n+1}x^n$$So we got what we wanted to prove. Although with $\eqref1$ (as you're looking for examples that don't require any real knowledge of calculus), we could instead write this as$$-\sum_{n\ge1}\dfrac{(-1)^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!}(-4x)^n$$using$$(2n-3)!!=\dfrac{(2n-2)!}{2^{n-1}(n-1)!}$$and then instead of having to try to explain the concept of factorials of the form $(n+1/2)!$, we can just simplify the proof by immediately writing$$1-\sqrt{1-4x}=-\sum_{n\ge1}\dfrac{(-1)^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!}(-4x)^n$$

$\endgroup$
5
  • 3
    $\begingroup$ I love this example! Also check out this link: math.ucr.edu/home/baez/week202.html $\endgroup$ Apr 4 at 17:33
  • 3
    $\begingroup$ I am going to echo the example in the previous comment, by adding that thinking about Catalan numbers as counting "binary rooted trees" is more visual and less confusing for students who may think of multiplication as commutative-only. $\endgroup$
    – Opal E
    Apr 4 at 19:27
  • $\begingroup$ @OpalE I guess that could make for a good, if not better introduction to the Catalan numbers before showing how the closed form of it is derived :) $\endgroup$
    – CrSb0001
    Apr 4 at 19:31
  • $\begingroup$ So the last equation would be “given” right? Seems not possible to prove the generalized binomial theorem without calculus (derivatives , Taylor expansion etc)? $\endgroup$
    – athos
    Apr 5 at 22:05
  • $\begingroup$ @athos I highly doubt that the generalized binomial theorem could be proved without calculus (you would have to come up with the formula for the analytic continuation of the factorial function first, which I also highly doubt is possible without calculus) $\endgroup$
    – CrSb0001
    Apr 5 at 22:07
4
$\begingroup$

I suggest using generating functions to find two dice whose sum has the same probability distribution as a pair of d6's. You can find this written up in the Sicherman Dice wikipage (where the section on "Mathematical justification" discusses generating functions and shows how to use them for this problem).


With regard to the earlier answer mentioning Catalan numbers as relates to their generating function, I asked a question some years ago on MathOverflow that may be of interest. See the question, answer, and the article linked on the accepted answer: MO 108216.

The article mentioned is:

An Unanticipated Decimal Expansion. Allen Schwenk, Math Horizons , Vol. 20, No. 1 (September 2012), pp. 10-12, https://www.jstor.org/stable/10.4169/mathhorizons.20.1.10.

(That article contains a bit about the Fibonacci generating function; it can be accessed without a paywall by using the sci-hub link currently here.)

$\endgroup$
1
  • 1
    $\begingroup$ Indeed this is quite interesting and surprising! $\endgroup$
    – athos
    Apr 25 at 20:16
2
$\begingroup$

How many ways is there to split a given sum of money into coins? How does this number grow?

If the available coins denominations are $n_1,n_2,\dots,n_k$, then the answer is given by coefficients of the expansion

$$(1+x^{n_1}+x^{2n_1}+\dots)(1+x^{n_2}+x^{2n_2}+\dots)\dots(1+x^{n_k}+x^{2n_k}+\dots)=\frac{1}{(1-x^{n_1})\dots(1-x^{n_k})}.$$

You can give a gentle introduction, with examples and finite sums instead. You can also handwave, or prove, depending on the level of your audience, the leading asymptotics for the growth: the right-hand side can be decomposed into a linear combination of fractions $(\xi-x)^m$, where $\xi$ is a root of unity. The larger $m$, the faster the growth. If $\gcd (n_1,\dots,n_k)=1$ then you can see that the largest possible $m$ will be $k$, for $\xi=1$, and all other $m$ will be smaller.

This touches on the partitions into integers (the case where all denomiantions $1,2,3,\dots$ are available) and the parition function $P(x)=\prod_{n\in\mathbb{N}}\frac{1}{1-x^n},$ leading to a serious advanced mathematics which truly cannot be done without generating functions, such as Hardy-Ramanujan and Rademacher's formulae for the number of partitions.

$\endgroup$
1

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.