Putnam 2024, Problem A-6

Let \( c_0, c_1, c_2, \ldots \) be the sequence defined so that
\[ \frac{1 - 3x - \sqrt{1 - 14x + 9x^2}}{4} = \sum_{k=0}^{\infty} c_k x^k \]
for sufficiently small \( x \). For a positive integer \( n \), let \( A \) be the \( n \)-by-\( n \) matrix with \( i, j \)-entry \( c_{i+j-1} \) for \( i \) and \( j \) in \( \{1, \ldots, n\} \). Find the determinant of \( A \).

Solution:
The determinant equals $10^{n(n-1)/2}$. We compute the corresponding determinant for the coefficients of the generic power series
$$f(x) := \sum_{n=1}^{\infty} c_n x^n, \quad c_1 = 1,$$
with associated continued fraction
$$\frac{a_0}{x^{-1} + b_0 + \frac{a_1}{x^{-1} + b_1 + \cdots}}, \quad a_0 = 1.$$

If we truncate by replacing $a_{n+1} = 0$, we get a rational function which can be written as $\frac{A_n(x^{-1})}{B_n(x^{-1})}$ where $A_n(x),B_n(x)$ are polynomials determined by the initial conditions
$$A_{-1}(x) = 1, A_0(x) = 0, \quad B_{-1}(x) = 0, B_0(x) = 1$$
and the recurrences
$$A_{n+1}(x) = (x + b_n)A_n(x) + a_nA_{n-1}(x) \quad (n > 0)$$
$$B_{n+1}(x) = (x + b_n)B_n(x) + a_nB_{n-1}(x) \quad (n > 0).$$

Since each additional truncation accounts for two more coefficients of the power series, we have
$$\frac{A_n(x^{-1})}{B_n(x^{-1})} = f(x) + O(x^{2n+1}),$$
or equivalently (since $B_n(x)$ is monic of degree $n$)
$$f(x)B_n(x^{-1}) - A_n(x^{-1}) = O(x^{n+1}). \tag{1}$$

We now reinterpret in the language of orthogonal polynomials. For a polynomial $P(x) = \sum_i P_i x^i$, define
$$\int_{\mu} P(x) = \sum_i P_i c_{i+1};$$
then the vanishing of the coefficient of $x^{i+1}$ in (1) (with $n := i$) implies that
$$\int_{\mu} x^i B_j(x) = 0 \quad (j < i).$$

By expanding $0 = \int_{\mu} x^{i-1}B_{i+1}(x)$ using the recurrence, we deduce that $\int_{\mu} x^i B_i(x) + a_i \int_{\mu} x^{i-1}B_{i-1}(x) = 0$, and so
$$\int_{\mu} x^i B_i(x) = (-1)^i a_1 \cdots a_i.$$

We deduce that
$$\int_{\mu} B_i(x)B_j(x) = \begin{cases} 0 & i \neq j \\ (-1)^i a_1 \cdots a_i & i = j. \end{cases} \tag{2}$$

In other words, for $U$ the $n \times n$ matrix such that $U_{ij}$ is the coefficient of $x^j$ in $B_i(x)$, the matrix $UAU^t$ is a diagonal matrix $D$ with diagonal entries $D_{i,i} = (-1)^{i-1}a_1 \cdots a_{i-1}$ for $i = 1,\ldots,n$. Since $U$ is a unipotent matrix, its determinant is $1$; we conclude that
$$\det(A) = \det(D) = (-1)^{n(n-1)/2} a_1^{n-1} \cdots a_{n-1}.$$

We now return to the sequence $\{c_n\}$ given in the problem statement, for which
$$f(x) = \frac{1 - 3x - \sqrt{1 - 14x + 9x^2}}{4}.$$

For
$$g(x) := \frac{1 - 7x - \sqrt{1 - 14x + 9x^2}}{2x},$$
we have
$$f(x) = \frac{1}{x^{-1} - 5 - g(x)}, \quad g(x) = \frac{10}{x^{-1} - 7 - g(x)}.$$

This means that the continued fraction is eventually periodic; in particular, $a_1 = a_2 = \cdots = -10$. Plugging into the general formula for $\det(A)$ yields the desired result. This yields the desired result.

**Reinterpretation.** (suggested by Bjorn Poonen) Given a formal Laurent series $\alpha = \sum_i a_i x^i$, define the matrices $H_n(\alpha) = (a_{i+j-1})_{i,j=1}^n$ and the determinants $h_n(\alpha) = \det H_n(\alpha)$. One can then recover the evaluation of the determinants from the following lemma.

**Lemma.** Suppose $\alpha = \sum_{i=1}^{\infty} a_i x^i$ is a formal power series with $a_i = 1$. Define the power series $\beta$ by $\alpha^{-1} = x^{-1} - \beta$. Then for all $n \geq 1$, $h_n(\alpha) = h_{n-1}(\beta)$.

*Proof.* For $m \geq 2$, by equating the coefficients of $x^m$ in the equality $x^{-1}\alpha = \alpha\beta + 1$, we obtain
$$a_{m+1} = \sum_{r=1}^{m} a_r b_{m-r}.$$

We now perform some row and column reduction on $H_n(\alpha)$ without changing its determinant. Starting with $H_n(\alpha)$, for $i = n, n-1, \ldots, 2$ in turn, for $k = 1, \ldots, i-1$ subtract $b_{i-1-k}$ times row $k$ from row $i$. In light of the recurrence relation, the resulting matrix $M = (m_{ij})$ has the property that for $i \geq 2$,
$$m_{ij} = a_{i+j-1} - \sum_{k=1}^{i-1} a_{j+k-1}b_{i-1s-k} = \sum_{r=1}^{j-1} a_r b_{i+j-2-r}.$$

In particular, $m_{i1} = 0$ for $i \geq 2$. Starting from $M$, for $j = 2, \ldots, n-1$ in turn, for $k = j+1, \ldots, n$ subtract $a_{k-j+1}$ times column $j$ from column $i$. The resulting matrix has first column $(1,0,\ldots,0)$ and removing its first row and column leaves $H_{n-1}(\beta)$, yielding the claimed equality. $\square$

**Remark.** A matrix $A$ whose $i,j$-entry depends only on $i+j$ is called a Hankel matrix. The above computation of the determinant of a Hankel matrix in terms of continued fractions is adapted from H.S. Wall, Analytic Theory of Continued Fractions, Theorems 50.1 and 51.1.

The same analysis shows that if we define the sequence $\{c_n\}_{n=1}^{\infty}$ by $c_1 = 1$ and
$$c_n = ac_{n-1} + b \sum_{i=1}^{n-1} c_i c_{n-i} \quad (n > 1),$$
then $a_n = -ab - b^2, b_n = -a - 2b$ for all $n > 0$ and so
$$\det(A) = (ab + b^2)^{n(n-1)/2};$$
the problem statement is the case $a = 3, b = 2$. The case $a = 0, b = 1$ yields the sequence of Catalan numbers; the case $a = 1, b = 1$ yields the Schröder numbers (OEIS sequence A006318).

There are a number of additional cases of Hankel determinants of interest in combinatorics. For a survey, see: A. Junod, Hankel determinants and orthogonal polynomials, Expositiones Mathematicae 21 (2003), 63-74.