Curious identity between the two kinds of Chebyshev polynomials

Question

I have found, by accident, an identity that relates a sum of Chebyshev polynomials of the first kind to a Chebyshev polynomial of the second kind. It goes as follows:

Given an integer partition of $n$, let $g_a$ be the number of times $a$ appears in said partition.${}^1$ Then the following identity holds for all $n \in\mathbb{N}$:

$$ U_n(x) = \sum_{\substack{n_i>0\\ \sum_i n_i = n}} \frac{1}{\prod_{a\in \{n_i\}} g_a!} \prod_{i=1} \frac{2}{n_i} T_{n_i}(x)\,. $$

The sum is over all integer partitions of $n$, the product is on all $n_i$'s in the partition, with repetitions.

I have a very roundabout way to prove this identity (I'll skip the details). The left hand side is obtained by contracting two symmetric traceless tensors of $SO(4)$. That is, letting $|x|=|y|=1$ and $x,y\in \mathbb{R}^4$ then $$ (x^{i_1}\cdots x^{i_n} - \mathrm{traces}) (y_{i_1}\cdots y_{i_n} - \mathrm{traces}) \propto U_n(x\cdot y)\,. $$ The right hand side instead comes from the same contraction but in spinor notation. Namely we let $$ \mathrm{x} = \left(\begin{matrix}x_3-x_4 & x_1 - i x_2 \\ x_1 + i x_2 & -x_3-x_4\end{matrix}\right)\,,\quad \bar{\mathrm{x}} = \epsilon\, \mathrm{x}\, \epsilon^T\,, $$ and $\mathrm{y}$ in a similar way ($\epsilon$ is the Levi Civita tensor). Then we introduce two dimensional spinors $\eta,\tilde{\eta}$ let $\partial_{\eta^\alpha}\eta^\beta = \delta_\alpha^\beta$ (similar for $\tilde{\eta}$) and finally $$ (\partial_\eta \mathrm{x} \partial_{\tilde{\eta}})^n (\eta \mathrm{y}\tilde{\eta})^n \sim \sum_{\substack{n_i>0\\ \sum_i n_i = n}} \# \prod_{i} \mathrm{tr}\,((\mathrm{x}\bar{\mathrm{y}})^{n_i})\,. $$ The sum over partitions comes from a combinatoric argument. Then it's a simple exercise to show that $\mathrm{tr}\,((\mathrm{x}\bar{\mathrm{y}})^n) \propto T_n(x\cdot y)$.

My questions are

1. Is this identity known already?
2. If not, could you come up with some more direct argument to prove it?

---

$\;{}^1$ For example, $(1,1,1,2,2,3)$ is an integer partition of $n=10$ with $g_1 =3,\, g_2=2,\,g_3=1$.

Answer 1

Here is how to prove it with more standard methods. First of all, let me restate your identity:

Definition. Let $\mathbb{N}=\left\{ 0,1,2,\ldots\right\} $. A partition shall mean an integer partition, i.e., a weakly decreasing finite list of positive integers. If $\lambda$ is a partition and $i$ is a positive integer, then $m_{i}\left( \lambda\right) $ shall mean the number of times that $i$ appears as entry of $\lambda$. (For example, $m_{3}\left( \left( 4,3,3,1\right) \right) =2$ and $m_{2}\left( \left( 4,3,3,1\right) \right) =0$.) The size $\left\vert \lambda\right\vert $ of a partition is defined to be the sum of all entries of $\lambda$. If $n\in\mathbb{N}$, then a partition of $n$ means a partition of size $n$. We write "$\lambda\vdash n$" for "$\lambda$ is a partition of $n$".

Definition. We let $T_n\left(x\right)$ denote the Chebyshev polynomials of the first kind, which can be defined (e.g.) by the recurrence $T_0\left(x\right) = 1$ and $T_1\left(x\right) = x$ and $T_{n+1}\left(x\right) = 2x T_n\left(x\right) - T_{n-1}\left(x\right)$. We let $U_n\left(x\right)$ denote the Chebyshev polynomials of the second kind, which can be defined (e.g.) by the recurrence $U_0\left(x\right) = 1$ and $U_1\left(x\right) = 2x$ and $U_{n+1}\left(x\right) = 2x U_n\left(x\right) - U_{n-1}\left(x\right)$.

Theorem 1. For any $n\in\mathbb{N}$, we have \begin{equation} U_{n}\left( x\right) =\sum_{\lambda=\left( \lambda_{1},\lambda_{2} ,\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \cdot\prod_{j=1}^{k}\left( 2T_{\lambda_{j}}\left( x\right) \right) . \end{equation}

To prove this, I will use two well-known generating-function identities for Chebyshev polynomials, both of which appear on the Wikipedia: \begin{equation} \sum_{n=0}^{\infty}T_{n}\left( x\right) t^{n}=\dfrac{1-tx}{1-2tx+t^{2}} \label{darij1.eq.T-gen} \tag{1} \end{equation} and \begin{equation} \sum_{n=0}^{\infty}U_{n}\left( x\right) t^{n}=\dfrac{1}{1-2tx+t^{2} }. \label{darij1.eq.U-gen} \tag{2} \end{equation} These are identities in the ring $\left( \mathbb{Q}\left[ x\right] \right) \left[ \left[ t\right] \right] $ of formal power series in the variable $t$ over the polynomial ring $\mathbb{Q}\left[ x\right] $. Both identities can easily be derived from the above recurrent definitions of $T_n\left(x\right)$ and $U_n\left(x\right)$.

Now, subtracting the equality $\underbrace{T_{0}\left( x\right) } _{=1}\underbrace{t^{0}}_{=1}=1$ from the identity \eqref{darij1.eq.T-gen}, we obtain \begin{equation} \sum_{n=1}^{\infty}T_{n}\left( x\right) t^{n}=\dfrac{1-tx}{1-2tx+t^{2} }-1=t\cdot\dfrac{x-t}{1-2tx+t^{2}}. \end{equation} Dividing both sides of this by $t$, we obtain \begin{equation} \sum_{n=1}^{\infty}T_{n}\left( x\right) t^{n-1} = \dfrac{x-t}{1-2tx+t^{2}}. \end{equation} Integrating both sides of this equality over $t$, we find \begin{align} \sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n} & =\int\dfrac {x-t}{1-2tx+t^{2}}dt\nonumber\\ & =\dfrac{1}{2}\log\dfrac{1}{1-2tx+t^{2}} \label{darij1.eq.T-ge2} \tag{3} \end{align} (as you can easily check by differentiation). (Note that this identity also appears on the Wikipedia, under the guise of $\sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n}=\log\dfrac{1}{\sqrt{1-2tx+t^{2}}}$, apparently because someone finds square roots simpler than division by $2$.)

Multiplying both sides of the equality \eqref{darij1.eq.T-ge2} by $2$, we obtain \begin{equation} 2\sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n}=\log\dfrac {1}{1-2tx+t^{2}}. \end{equation} Hence, \begin{equation} \log\dfrac{1}{1-2tx+t^{2}}=2\sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n}=\sum_{n=1}^{\infty}2T_{n}\left( x\right) \dfrac{t^{n}}{n}, \end{equation} so that \begin{equation} \dfrac{1}{1-2tx+t^{2}}=\exp\left( \sum_{n=1}^{\infty}2T_{n}\left( x\right) \dfrac{t^{n}}{n}\right) . \end{equation} Hence, \eqref{darij1.eq.U-gen} becomes \begin{equation} \sum_{n=0}^{\infty}U_{n}\left( x\right) t^{n}=\dfrac{1}{1-2tx+t^{2}} =\exp\left( \sum_{n=1}^{\infty}2T_{n}\left( x\right) \dfrac{t^{n}} {n}\right) . \label{darij1.eq.T-ge3} \tag{4} \end{equation}

Now, we recall one of the staple formulas of algebraic combinatorics (probably in EC or Wilf or similar sources):

Proposition 2. Let $R$ be a commutative $\mathbb{Q}$-algebra (for example, $\mathbb{Q}$ or $\mathbb{Q}\left[ x\right] $). Let $b_{1},b_{2},b_{3} ,\ldots\in R$ and $c_{0},c_{1},c_{2},\ldots\in R$ be such that \begin{equation} \sum_{n=0}^{\infty}c_{n}t^{n}=\exp\left( \sum_{n=1}^{\infty}b_{n}\dfrac {t^{n}}{n}\right) \end{equation} in the ring $R\left[ \left[ t\right] \right] $ of formal power series. Then, \begin{equation} c_{n}=\sum_{\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \cdot\prod_{j=1}^{k}b_{\lambda_{j}} \end{equation} for each $n\in\mathbb{N}$.

Proof of Proposition 2. An infinite sequence $\left( k_{1},k_{2} ,k_{3},\ldots\right) \in\mathbb{N}^{\infty}$ of nonnegative integers will be called a weak composition if all but finitely many $i\geq1$ satisfy $k_{i}=0$. There is a bijection \begin{align} \left\{ \text{partitions}\right\} & \rightarrow\left\{ \text{weak compositions}\right\} ,\nonumber\\ \lambda & \mapsto\left( m_{1}\left( \lambda\right) ,m_{2}\left( \lambda\right) ,m_{3}\left( \lambda\right) ,\ldots\right) \label{darij1.pf.p2.1} \tag{5} \end{align} (since any partition $\lambda$ is uniquely determined by the numbers $m_{1}\left( \lambda\right) ,m_{2}\left( \lambda\right) ,m_{3}\left( \lambda\right) ,\ldots$ which record how often each positive integer appears in $\lambda$). We notice that any partition $\lambda$ satisfies \begin{equation} 1m_{1}\left( \lambda\right) +2m_{2}\left( \lambda\right) +3m_{3}\left( \lambda\right) +\cdots=\left\vert \lambda\right\vert \label{darij1.pf.p2.2} \tag{6} \end{equation} (because $\left\vert \lambda\right\vert $ is the sum of all entries of $\lambda$, while $1m_{1}\left( \lambda\right) +2m_{2}\left( \lambda\right) +3m_{3}\left( \lambda\right) +\cdots$ is what becomes of this sum after equal addends are bunched together). Moreover, any partition $\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) $ satisfies \begin{equation} \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }=\prod_{j=1} ^{k}b_{\lambda_{j}} \label{darij1.pf.p2.3} \tag{7} \end{equation} (for a similar reason: the product $\prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }$ is what will become of the product $\prod_{j=1} ^{k}b_{\lambda_{j}}$ if you bunch factors corresponding to equal entries of $\lambda$ together).

We have the following product rule (i.e., analogue of the distributivity law) for infinite products of infinite sums: If $\left( a_{i,k}\right) _{i\geq1\text{ and }k\geq0}$ is a family of elements of $R\left[ \left[ t\right] \right] $ satisfying $a_{i,0}=1$ for each $i\geq1$, then \begin{equation} \prod_{i=1}^{\infty}\sum_{k=0}^{\infty}a_{i,k}=\sum_{\substack{\left( k_{1},k_{2},k_{3},\ldots\right) \text{ is a}\\\text{weak composition}} }\prod_{i=1}^{\infty}a_{i,k_{i}}, \label{darij1.pf.p2.prodrule} \tag{8} \end{equation} provided that everything formally converges (i.e., for each given $N\in\mathbb{N}$, all but finitely many pairs $\left( i,k\right) \in\left\{ 1,2,3,\ldots\right\} ^{2}$ satisfy $t^N \mid a_{i,k}$ in $R\left[\left[t\right]\right]$).

We have \begin{align} \sum_{n=0}^{\infty}c_{n}t^{n} & =\exp\left( \sum_{n=1}^{\infty}b_{n} \dfrac{t^{n}}{n}\right) =\prod_{n=1}^{\infty}\underbrace{\exp\left( b_{n}\dfrac{t^{n}}{n}\right) }_{\substack{=\sum_{k=0}^{\infty}\dfrac{1} {k!}\left( b_{n}\dfrac{t^{n}}{n}\right) ^{k}\\\text{(since }\exp z=\sum_{k=0}^{\infty}\dfrac{1}{k!}z^{k}\text{)}}}\nonumber\\ & \qquad \left(\text{since $\exp\left(\sum_{i\in I} a_i\right) = \prod_{i\in I} \exp a_i$ for any family $\left(a_i\right)_{i\in I}$}\right) \nonumber\\ & =\prod_{n=1}^{\infty}\sum_{k=0}^{\infty}\dfrac{1}{k!}\left( b_{n} \dfrac{t^{n}}{n}\right) ^{k}=\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}\dfrac {1}{k!}\underbrace{\left( b_{i}\dfrac{t^{i}}{i}\right) ^{k}}_{=\dfrac {b_{i}^{k}t^{ik}}{i^{k}}}\nonumber\\ & \qquad\left( \text{here, we have renamed the index }n\text{ as }i\right) \nonumber\\ & =\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}\dfrac{1}{k!}\cdot\dfrac{b_{i} ^{k}t^{ik}}{i^{k}}=\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}\dfrac{b_{i} ^{k}t^{ik}}{i^{k}k!}\nonumber\\ & =\sum_{\substack{\left( k_{1},k_{2},k_{3},\ldots\right) \text{ is a}\\\text{weak composition}}}\prod_{i=1}^{\infty}\dfrac{b_{i}^{k_{i}} t^{ik_{i}}}{i^{k_{i}}k_{i}!}\nonumber\\ & \qquad\left( \text{by the product rule \eqref{darij1.pf.p2.prodrule}, applied to }a_{i,k}=\dfrac{b_{i}^{k}t^{ik}}{i^{k}k!}\right) \nonumber\\ & =\sum_{\lambda\text{ is a partition}}\underbrace{\prod_{i=1}^{\infty} \dfrac{b_{i}^{m_{i}\left( \lambda\right) }t^{im_{i}\left( \lambda\right) }}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}}_{=\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \left( \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) \left( \prod_{i=1}^{\infty}t^{im_{i}\left( \lambda\right) }\right) }\nonumber\\ & \qquad\left( \begin{array} [c]{c} \text{here, we have substituted }\left( m_{1}\left( \lambda\right) ,m_{2}\left( \lambda\right) ,m_{3}\left( \lambda\right) ,\ldots\right) \\ \text{for }\left( k_{1},k_{2},k_{3},\ldots\right) \text{ in the sum, due to the bijection \eqref{darij1.pf.p2.1}} \end{array} \right) \nonumber\\ & =\sum_{\lambda\text{ is a partition}}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \left( \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) \underbrace{\left( \prod_{i=1}^{\infty}t^{im_{i}\left( \lambda\right) }\right) }_{\substack{=t^{1m_{1}\left( \lambda\right) +2m_{2}\left( \lambda\right) +3m_{3}\left( \lambda\right) +\cdots}\\=t^{\left\vert \lambda\right\vert }\\\text{(by \eqref{darij1.pf.p2.2})}}}\nonumber\\ & =\sum_{\lambda\text{ is a partition}}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \left( \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) t^{\left\vert \lambda\right\vert }. \label{darij1.pf.p2.6} \tag{9} \end{align}

Now, let $n\in\mathbb{N}$. Comparing coefficients of $t^{n}$ on both sides of the equality \eqref{darij1.pf.p2.6}, we obtain \begin{align*} c_{n} & =\underbrace{\sum_{\substack{\lambda\text{ is a partition;} \\\left\vert \lambda\right\vert =n}}}_{\substack{=\sum_{\lambda\vdash n}\\\text{(since the partitions of }n\\\text{are precisely the partitions }\lambda\\\text{with }\left\vert \lambda\right\vert =n\text{)}}}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\\ & =\sum_{\lambda\vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \prod_{i=1}^{\infty }b_{i}^{m_{i}\left( \lambda\right) }\\ & =\sum_{\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \underbrace{\left( \prod _{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) } _{\substack{=\prod_{j=1}^{k}b_{\lambda_{j}}\\\text{(by \eqref{darij1.pf.p2.3})}}}\\ & =\sum_{\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \prod_{j=1}^{k}b_{\lambda_{j}}. \end{align*} This proves Proposition 2. $\blacksquare$

Proof of Theorem 1. Recall the identity \eqref{darij1.eq.T-ge3}. Thus, Proposition 2 (applied to $R=\mathbb{Q}\left[ x\right] $ and $c_{n} =U_{n}\left( x\right) $ and $b_{n}=2T_{n}\left( x\right) $) yields that \begin{equation} U_{n}\left( x\right) =\sum_{\lambda=\left( \lambda_{1},\lambda_{2} ,\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \cdot\prod_{j=1}^{k}\left( 2T_{\lambda_{j}}\left( x\right) \right) \end{equation} for each $n\in\mathbb{N}$. This proves Theorem 1. $\blacksquare$

Answer 2

I think I can sketch a shorter proof.

Let $z_j = x_j+x_j^{-1}$, and let $p_m$ and $h_m$ denote the power-sum and complete homogeneous symmetric polynomial.

Then (see e.g p.3 in this preprint) $$ 2 T_m(z_j/2) = p_m(x_j,x_j^{-1}) \text{ and } U_m(z_j/2) = h_m(x_j,x_j^{-1}) $$

Now, we can use the Newton identities, to express $h_m$ in terms of the power-sum symmetric functions. This gives a relation between the $U_m$ and the $T_m$.

Looking at your formula, it is very similar to the Newton identity.