Solving Problems Submitted to MAA Journals (Part 3)

The following problem appeared in Volume 53, Issue 4 (2022) of The College Mathematics Journal.

Define, for every non-negative integer $n$ , the $n$ th Catalan number by

$C_n := \displaystyle \frac{1}{n+1} {2n \choose n}$ .

Consider the sequence of complex polynomials in $z$ defined by $z_k := z_{k-1}^2 + z$ for every non-negative integer $k$ , where $z_0 := z$ . It is clear that $z_k$ has degree $2^k$ and thus has the representation

$z_k =\displaystyle \sum_{n=1}^{2^k} M_{n,k} z^n$ ,

where each $M_{n,k}$ is a positive integer. Prove that $M_{n,k} = C_{n-1}$ for $1 \le n \le k+1$ .

This problem appeared in the same issue as the probability problem considered in the previous two posts. Looking back, I think that the confidence that I gained by solving that problem gave me the persistence to solve this problem as well.

My first thought when reading this problem was something like “This involves sums, polynomials, and binomial coefficients. And since the sequence is recursively defined, it’s probably going to involve a proof by mathematical induction. I can do this.”

My second thought was to use Mathematica to develop my own intuition and to confirm that the claimed pattern actually worked for the first few values of $z_k$ .

As claimed in the statement of the problem, each $z_k$ is a polynomial of degree $2^k$ without a nontrivial constant term. Also, for each $z_k$ , the term of degree $n$ , for $1 \le n \le k+1$ , has a coefficient that is independent of $k$ which equal to $C_{n-1}$ . For example, for $z_4$ , the coefficient of $z^5$ (in orange above) is equal to

$C_4 = \displaystyle \frac{1}{5} {8 \choose 4} = \frac{8!}{4! 4! \cdot 5} = \frac{40320}{2880} = 14$ ,

and the problem claims that the coefficient of $z^5$ will remain 14 for $z_5, z_6, z_7, \dots$

Confident that the pattern actually worked, all that remained was pushing through the proof by induction.

We proceed by induction on $k$ . The statement clearly holds for $k=1$ :

$z_1 = z_0^2 + z = z + z^2 = C_0 z + C_1 z^2$ .

Although not necessary, I’ll add for good measure that

$z_2 = z_1^2 + z = (z^2+z)^2 + z = z + z^2 + 2z^3 + z^4 = C_0 z + C_1 z^2 + C_2 z^3 + z^4$

and

$z_3 = z^2 + z = (z^4+2z^3+z^2+z)^2 + z$

$= z + z^2 + 2z^3 + 5z^4 + 6z^5 + 6z^6 + 4z^7 + z^8$

$= C_0 z + C_1 z^2 + C_2 z^3 + C_3 z^4 + 6z^5 + 6z^6 + 4z^7 + z^8.$

This next calculation illustrates what’s coming later. In the previous calculation, the coefficient of $z^4$ is found by multiplying out

$(z^4+2z^3+z^2+z)(z^4+2z^3+z^2+z)$ .

This is accomplished by examining all pairs, one from the left product and one from the right product, so that the exponent works out to be $z^4$ . In this case, it’s

$(2z^3)(z) + (z^2)(z^2) + (z)(2z^3) = 5z^4$ .

For the inductive step, we assume that, for some $k \ge 1$ , $M_{n,k} = C_{n-1}$ for all $1 \le n \le k+1$ , and we define

$z_{k+1} = z + \left( M_{1,k} z + M_{2,k} z^2 + M_{3,k} z^3 + \dots + M_{2^k,k} z^{2^k} \right)^2$

Our goal is to show that $M_{n,k+1} = C_{n-1}$ for $n = 1, 2, \dots, k+2$ .

For $n=1$ , the coefficient $M_{1,k+1}$ of $z$ in $z_{k+1}$ is clearly 1, or $C_0$ .

For $2 \le n \le k+2$ , the coefficient $M_{n,k+1}$ of $z^n$ in $z_{k+1}$ can be found by expanding the above square. Every product of the form $M_{j,k} z^j \cdot M_{n-j,k} z^{n-j}$ will contribute to the term $M_{n,k+1} z^n$ . Since $n \le k+2 \le 2^k+1$ (since $k \ge 1$ ), the values of $j$ that will contribute to this term will be $j = 1, 2, \dots, n-1$ . (Ordinarily, the $z^0$ and $z^n$ terms would also contribute; however, there is no $z^0$ term in the expression being squared). Therefore, after using the induction hypothesis and reindexing, we find