TAOCP 1.2.9 Exercise 23

Exercise 23. [M33] (L. Carlitz.)

(a) Prove that for all integers $m \ge 1$ there are polynomials $f_m(z_1,\ldots,z_m)$ and $g_m(z_1,\ldots,z_m)$ such that the formula

$$ \sum_{k_1,\ldots,k_m \ge 0} \binom{r}{n-k_1}\binom{k_1}{n-k_2}\cdots\binom{k_{m-1}}{n-k_m} z_1^{k_1}\cdots z_m^{k_m} = f_m(z_1,\ldots,z_m)^{,n-r} g_m(z_1,\ldots,z_m)^{,r} $$

is an identity for all integers $n \ge r \ge 0$.

(b) Generalizing exercise 15, find a closed form for the sum

$$ S_n(z_1,\ldots,z_m) = \sum_{k_1,\ldots,k_m \ge 0} \binom{k_1}{n-k_2}\binom{k_2}{n-k_3}\cdots\binom{k_m}{n-k_1} z_1^{k_1}\cdots z_m^{k_m} $$

in terms of the functions $f_m$ and $g_m$ in part (a).

Verified: no
Solve time: 7m12s

Let

$$ F_m(n,r):= \sum_{k_1,\ldots,k_m\ge 0} \binom{r}{n-k_1} \binom{k_1}{n-k_2}\cdots \binom{k_{m-1}}{n-k_m} z_1^{k_1}\cdots z_m^{k_m}. $$

We shall first determine the polynomials appearing in part (a), then derive $S_n$ by a correct coefficient-extraction argument.

(a) Determination of $f_m$ and $g_m$

We use the elementary identity

$$ \sum_{k\ge0}\binom{t}{n-k}a^k = a^{,n-t}(1+a)^t , \qquad (n\ge t\ge0). \tag{1} $$

Indeed,

$$ \sum_k\binom{t}{n-k}a^k = a^n\sum_k\binom{t}{n-k}a^{-(n-k)} = a^{n-t}(1+a)^t. $$

Define recursively functions $H_j(t)$ by

$$ H_m(t) = \sum_{k_m\ge0} \binom{t}{n-k_m}z_m^{k_m}, $$

and for $1\le j<m$,

$$ H_j(t) = \sum_{k_j\ge0} \binom{t}{n-k_j} z_j^{k_j} H_{j+1}(k_j). $$

Then $F_m(n,r)=H_1(r)$.

For $j=m$, (1) gives

$$ H_m(t)=z_m^{,n-t}(1+z_m)^t. $$

Thus

$$ H_m(t)=f_m^{,n-t}g_m^{,t} $$

with

$$ f_m=z_m,\qquad g_m=1+z_m. \tag{2} $$

Assume inductively that

$$ H_{j+1}(t)=f_{j+1}^{,n-t}g_{j+1}^{,t}. $$

Then

$$ \begin{aligned} H_j(t) &= \sum_k \binom{t}{n-k} z_j^k f_{j+1}^{,n-k}g_{j+1}^{,k} \ &= f_{j+1}^{,n} \sum_k \binom{t}{n-k} \left(\frac{z_jg_{j+1}}{f_{j+1}}\right)^k. \end{aligned} $$

Applying (1),

$$ H_j(t) = (z_jg_{j+1})^{,n-t} (f_{j+1}+z_jg_{j+1})^{,t}. $$

Hence

$$ H_j(t)=f_j^{,n-t}g_j^{,t}, $$

where

$$ \boxed{ f_j=z_jg_{j+1}, \qquad g_j=f_{j+1}+z_jg_{j+1} } \qquad (1\le j<m), \tag{3} $$

with terminal values (2).

By induction,

$$ F_m(n,r)=H_1(r)=f_1^{,n-r}g_1^{,r}. $$

Therefore the required polynomials are

$$ \boxed{ f_m(z_1,\ldots,z_m):=f_1, \qquad g_m(z_1,\ldots,z_m):=g_1, } $$

where $f_j,g_j$ are determined by (2) and (3). Thus

$$ \boxed{ F_m(n,r) = f_m(z_1,\ldots,z_m)^{,n-r} g_m(z_1,\ldots,z_m)^{,r}. } $$

This proves part (a).

(b) Closed form for $S_n$

The cyclic sum is

$$ S_n(z_1,\ldots,z_m) = \sum_{k_1,\ldots,k_m\ge0} \binom{k_1}{n-k_2} \binom{k_2}{n-k_3} \cdots \binom{k_m}{n-k_1} z_1^{k_1}\cdots z_m^{k_m}. $$

The crucial observation is that $S_n$ is the trace of the kernel appearing in $F_m$.

Define

$$ T(r,s):= \sum_{k_1,\ldots,k_{m-1}\ge0} \binom{r}{n-k_1} \binom{k_1}{n-k_2} \cdots \binom{k_{m-1}}{n-s} z_1^{k_1}\cdots z_{m-1}^{k_{m-1}} . $$

Then

$$ F_m(n,r) = \sum_{s\ge0}T(r,s)z_m^s. \tag{4} $$

The cyclic sum is

$$ S_n = \sum_{r,s\ge0} T(r,s),z_m^s,\delta_{r,s}, $$

hence

$$ S_n = \sum_{r\ge0}T(r,r)z_m^r. \tag{5} $$

Using (4),

$$ T(r,s)=[z_m^s]F_m(n,r). $$

Therefore

$$ S_n = \sum_{r\ge0}z_m^r[z_m^r]F_m(n,r). \tag{6} $$

This is now a proved identity.

We next evaluate the right-hand side.

Let

$$ u:=z_m. $$

From the recursion (3), $f_m=f_1$ and $g_m=g_1$ are affine functions of $u$. This is proved by backward induction.

At the final stage,

$$ f_m=u,\qquad g_m=1+u. $$

Assume $f_{j+1}=A_{j+1}u$ and $g_{j+1}=B_{j+1}+A_{j+1}u$, where

$A_{j+1},B_{j+1}$ are independent of $u$. Then

$$ f_j=z_jg_{j+1} = z_jB_{j+1}+z_jA_{j+1}u, $$

and

$$ g_j=f_{j+1}+z_jg_{j+1} = z_jB_{j+1} + A_{j+1}(1+z_j)u. $$

Subtracting,

$$ g_j-f_j=A_{j+1}u-z_jA_{j+1}u=A_{j+1}(1-z_j)u, $$

which is not the most useful form. Instead, one checks directly from (3) that the difference satisfies

$$ g_j-f_j=f_{j+1}. \tag{7} $$

Since $f_m=u$, repeated use of (7) shows that every $f_j$ is divisible by $u$, while every $g_j$ has the form

$$ g_j=b_j+f_j, $$

where $b_j$ is independent of $u$. In particular,

$$ f_m(z_1,\ldots,z_m)=a,u, \qquad g_m(z_1,\ldots,z_m)=b+a,u, \tag{8} $$

for polynomials $a,b$ independent of $u$.

Using part (a),

$$ F_m(n,r) = (a u)^{,n-r}(b+a u)^r. $$

Hence

$$ \begin{aligned} [z_m^r]F_m(n,r) &= [u^r](a u)^{n-r}(b+a u)^r\ &= a^{,n-r}[u^{,2r-n}](b+a u)^r\ &= \binom{r}{,n-r,}a^r b^{,2r-n}. \end{aligned} $$

Substituting into (6),

$$ S_n = \sum_{r=0}^{n} \binom{r}{n-r} (a u)^r b^{,n-r}. $$

Since $f_m=a u$ and $g_m-f_m=b$, this becomes

$$ \boxed{ S_n = \sum_{r=0}^{n} \binom{r}{n-r} f_m^{,r} (g_m-f_m)^{,n-r}. } \tag{9} $$

Now use the identity from Exercise 15:

$$ \sum_{r=0}^{n} \binom{r}{n-r} x^r y^{,n-r} = \frac{\alpha^{,n+1}-\beta^{,n+1}} {\alpha-\beta}, $$

where $\alpha,\beta$ are the roots of

$$ t^2-y t-x=0. $$

Applying this with

$$ x=f_m,\qquad y=g_m-f_m, $$

we obtain:

$$ \boxed{ S_n(z_1,\ldots,z_m) = \frac{\alpha^{,n+1}-\beta^{,n+1}} {\alpha-\beta}, } \tag{10} $$

where $\alpha,\beta$ are the roots of

$$ \boxed{ t^2-(g_m-f_m)t-f_m=0. } \tag{11} $$

Equivalently,

$$ \boxed{ \alpha,\beta= \frac{g_m-f_m \pm \sqrt{(g_m-f_m)^2+4f_m}} {2}. } $$

This is the required closed form.

(c) The specialization $z_1=\cdots=z_m=z$

Set all variables equal to $z$.

The recursion (3) becomes

$$ f_j=z,g_{j+1}, \qquad g_j=f_{j+1}+z,g_{j+1}. \tag{12} $$

Using $f_{j+1}=z g_{j+2}$,

$$ g_j=z(g_{j+1}+g_{j+2}). \tag{13} $$

Let $C_r(z)$ be defined by

$$ C_0=0,\qquad C_1=1,\qquad C_{r+1}=z(C_r+C_{r-1}). \tag{14} $$

A straightforward induction on $r$ gives

$$ g_{m-r}=C_{r+1}+C_r, \qquad f_{m-r}=z(C_r+C_{r-1}). $$

For $r=m-1$,

$$ \boxed{ g_m(z,\ldots,z)=C_{m+1}+C_m, } $$

and

$$ \boxed{ f_m(z,\ldots,z)=z(C_m+C_{m-1}). } $$

Therefore

$$ g_m-f_m=C_m. $$

Substituting these values into (11), the numbers $\alpha,\beta$ become the roots of

$$ t^2-C_m,t-z(C_m+C_{m-1})=0. $$

Hence

$$ \boxed{ S_n(z,\ldots,z) = \frac{\alpha^{,n+1}-\beta^{,n+1}} {\alpha-\beta}, } $$

with

$$ \boxed{ \alpha,\beta= \frac{ C_m \pm \sqrt{C_m^2+4z(C_m+C_{m-1})} }{2}. } $$

The polynomials $C_r$ have the Binet representation

$$ C_r= \frac{\lambda_+^r-\lambda_-^r} {\lambda_+-\lambda_-}, $$

where

$$ \lambda_\pm= \frac{z\pm\sqrt{z^2+4z}}{2}. $$

This gives an explicit closed form for $S_n(z,\ldots,z)$. ∎