Expansion coefficients

Question

Suppose that we are given the function $f(x)$ in the following product form: $$f(x) = \prod_{k = -K}^K (1-a^k x)\,,$$ Where $a$ is some real number.

I would like to find the expansion coefficients $c_n$, such that: $$f(x) = \sum_{n = 0}^{2K+1} c_n x^n\,.$$

A closed form solution for $c_n$, or at least a relation between the coefficients $c_n$ (e.g. between $c_n$ and $c_{n+1}$) would be great!

Answer 1

Let the function $f_n(x)$ be given by $$ f_n(x) = \prod_{k=-n}^{n} \left( 1 - a^k x \right) $$ Since it is clear that it is a polynomial of degree $2 n +1$, it can be expressed as: $$ f_n(x) = \sum_{k=0}^{2n+1} c_{n,k} x^k $$ in some yet unknown coefficients $c_{n,k}$. For these coefficients it is easy to see that $c_{n,0}=1$ and $c_{n,2n+1}=-1$. More generally one could show that $c_{n,k} = -c_{n,2n+1-k}$.

The functions for different values of $n$ are related by: $$ f_n(x) = f_{n-1}(x) * \left(1 - a^n x\right)\left(1-a^{-n}x\right) = f_{n-1} * \left[1 - \left(a^n + a^{-n}\right)x + x^2\right] $$ If we now substitute the expansion in to this expression and group the terms with the same power of $x$ on both the left and right side we can find a recurrence relation between the coefficients $c_{n,k}$ of successive functions: $$ c_{n,k} = c_{n-1,k} - \left(a^n + a^{-n}\right) c_{n-1,k-1} + c_{n-1,k-2} $$ Together with the condition $c_{0,0} = 1$ and $c_{0,k}$ for $k \neq 0$ this completely specifies the coefficients and one could set up a program to evaluate them, because in general a simple and compact expression for them might not exist.

In this particular case, however, there is such a "simple" expression: $$ c_{n,k} =\frac{\prod_{i=0}^{k-1} \left(a^{2n+1} - a^i \right)}{a^{k n}\prod_{i=1}^{k} \left(1 - a^i \right)} $$ with $0 \leq k \leq 2n+1$ and the product by definition is unity if no terms are present. By rearranging the limits of products a few other but equivalent expressions exist.

Deriving them is a lot of work so I simply presented them. The fact that they are correct however, is a lot easier to show. For this one first observes that $c_{0,0}=1$. From there we only need to show that the expression satisfies the recurrence relation shown above and the correctness follows from induction.

I leave that proof as an exercise, but give the following hint. In the recurrence relation there are three coefficients on the right hand side for the same value of $n$. If you compare the coefficients $c_{n-1,k}$, $c_{n-1,k-1}$, and $c_{n-1,k-2}$ there are quite a few factors from the numerator and denominator that they have in common and which also appear in $c_{n,k}$. The simplest way to see such a thing is to write the recurrence relation out for some chosen values for $n$ and $k$.

As another remark consider $c_{n,k}$ for $k>n$, then the number of factors in the numerator and denominator keep on growing which appear to lead to very long expressions. This is however not the case and can be seen as well if you write all the factors out for some particular values of $n$ and $k$.

Answer 2

Well, we have that - we need to suppose that $a\neq0$: $$f(x)=\prod_{k=-K}^K(1-a^kx)=(1-a^{-K}x)(1-a^{-K+1}x)\dots(1-a^Kx)$$ We can expand this product to a sum of powers of $x$, by considering in how many ways can we get $x^n$, where $n=0,1,2,\dots,2K+1$.

While expanding this product, we take each time exactly one of either $1$ or $-a^kx$ from each parenthesis and we multiply them. So, to take $x^n$, we need to take exactly $n$ times $-a^kx$ and $2K+1-n$ time $1$.

Now, we have $b_n=\binom{2K+1}{n}$ choices that give us exactly $n$ out of the $2K+1$ $(-a^kx)$'s, so, we can see that: $$f(x)=\sum_{n=0}^{2K+1}(-1)^n\left(\sum_{m=1}^{b_n}a^{s_{m,n}}\right)x^n$$ where $s_{m,n}$ is a - different for every $m$ - sum of $n$ distinct numbers from $\{-K,-K+1,\dots,K\}$.

From now own one can elaborate on the latter relation.

Answer 3

We have that $$ \bbox[lightyellow] { \eqalign{ & f(x) = \prod\limits_{k\, = \, - K}^K {\left( {1 - a^{\;k} x} \right)} = \prod\limits_{k\, = \, - K}^K {a^{\;k} \left( {a^{\; - k} - x} \right)} = \cr & = \left( {\prod\limits_{k\, = \, - K}^K {a^{\;k} } } \right)\;\prod\limits_{k\, = \, - K}^K {\left( {a^{\; - k} - x} \right)} = \left( {\prod\limits_{k\, = \, - K}^K {a^{\;k} } } \right)\;\left( { - 1} \right)^{2K + 1} \prod\limits_{k\, = \, - K}^K {\left( {x - a^{\; - k} } \right)} = \cr & = - \left( {\prod\limits_{k\, = \, - K}^K {a^{\;k} } } \right)\;\prod\limits_{k\, = \, - K}^K {\left( {x - a^{\; - k} } \right)} = - \prod\limits_{k\, = \, - K}^K {\left( {x - a^{\; - k} } \right)} = - \prod\limits_{k\, = \, - K}^K {\left( {x - a^{\;k} } \right)} = \cr & = - \left( {x - 1} \right)\prod\limits_{k\, = \,1}^K {\left( {x - a^{\;k} } \right)} \prod\limits_{k\, = \,1}^K {\left( {x - \left( {{1 \over a}} \right)^{\;k} } \right)} = \cr & = - {1 \over {\left( {x - 1} \right)}}\prod\limits_{k\, = \,0}^K {\left( {x - a^{\;k} } \right)} \prod\limits_{k\, = \,0}^K {\left( {x - \left( {{1 \over a}} \right)^{\;k} } \right)} = \cr & = {{\left( { - 1} \right)^{\,K} } \over {\left( {x - 1} \right)}}a^{\, - \,\left( {\scriptstyle K + 1 \atop \scriptstyle 2} \right)} \left( {\prod\limits_{k\, = \,0}^K {\left( {x - a^{\;k} } \right)} } \right)^{\,2} \cr} }$$ because $$ \prod\limits_{k\, = \,0}^K {\left( {x - a^{\;k} } \right)} = \left( { - 1} \right)^{\,K + 1} a^{\,\left( {\scriptstyle K + 1 \atop \scriptstyle 2} \right)} \prod\limits_{k\, = \,0}^K {\left( {x - \left( {{1 \over a}} \right)^{\;k} } \right)} $$

Then the $$ \bbox[lightyellow] { \prod\limits_{k\, = \,0}^{n - 1} {\left( {1 - xq^{\;k} } \right)} }$$ is the q-Pochammer Symbol $(x;\,q)_n$.

We can get the coefficients of the polynomial $$ \bbox[lightyellow] { f(x) = - \prod\limits_{k\, = \, - K}^K {\left( {x - a^{\;k} } \right)} = - \sum\limits_{j\, = \,0}^{2K + 1} {c_{\,j} \;x^{\,j} } }$$

by means of the Vieta's Formulas $$ \bbox[lightyellow] { \left\{ \matrix{ c_{\;2K + 1} = 1 \hfill \cr \left( { - 1} \right)^{\,k} c_{\;2K + 1 - k} \quad \left| {\;1 \le k} \right.\quad = \sum\limits_{ - K\, \le \,j_{\,1} \, < \,j_{\,2} \, < \, \cdots \, < \,j_{\,k} \, \le \,K} {a^{\;j_{\,1} \, + \,j_{\,2} \, + \, \cdots \, + \,j_{\,k} } } \hfill \cr} \right. }$$

Now $$ \bbox[lightyellow] { \sum\limits_{\left\{ \begin{subarray}{l} \;1\, \leqslant \,l\, \leqslant \,k \\ \; - K\, \leqslant \,j_{\,1} \, < \,j_{\,2} \, < \, \cdots \, < \,j_{\,k} \, \leqslant \,K \end{subarray} \right.} {\;j_{\,l} \,\,} = - k\left( {K + 1} \right) + \sum\limits_{\left\{ \begin{subarray}{l} \;1\, \leqslant \,l\, \leqslant \,k \\ \;1\, \leqslant \,j_{\,1} \, < \,j_{\,2} \, < \, \cdots \, < \,j_{\,k} \, \leqslant \,2K + 1 \end{subarray} \right.} {\;j_{\,l} \,\,} }$$ and we are left to evaluate the last sum.
That is, the sum of the elements of all the k-subsets of the set $\left\{ {1,\,2,\, \cdots ,\,2K + 1} \right\}$.

The total number of k-subsets is $$ N_{k - subs} = \left( \matrix{ 2K + 1 \cr k \cr} \right) $$ The number of k-subsets containing a given element $j$ clearly is $$ N_{j\, \in \;k - subs} = \left( \matrix{ 2K \cr k - 1 \cr} \right) $$

Thus the sum we are looking for is $$ \bbox[lightyellow] { \begin{gathered} S(k,2K + 1) = - k\left( {K + 1} \right) + \sum\limits_{\left\{ \begin{subarray}{l} \;1\, \leqslant \,l\, \leqslant \,k \\ \;1\, \leqslant \,j_{\,1} \, < \,j_{\,2} \, < \, \cdots \, < \,j_{\,k} \, \leqslant \,2K + 1 \end{subarray} \right.} {\;j_{\,l} \,\,} = \hfill \\ = - k\left( {K + 1} \right) + \left( \begin{gathered} 2K \\ k - 1 \\ \end{gathered} \right)\sum\limits_{\;1\, \leqslant \,j\, \leqslant \,2K + 1} {\;j\,} = \left( \begin{gathered} 2K \\ k - 1 \\ \end{gathered} \right)\left( \begin{gathered} 2K + 2 \\ 2 \\ \end{gathered} \right) - k\left( {K + 1} \right) \hfill \\ \end{gathered} }$$

Answer 4

We derive a representation of $c_j$ in \begin{align*} f_K(x)=\prod_{k=-K}^K(1-a^kx)=\sum_{j=0}^{2K+1}\color{blue}{c_j}x^j\qquad\qquad \qquad K\geq 0 \end{align*} based upon the q-Pochhammer symbol $(x;a)_K$.

According to the referred Wiki page the following is valid. \begin{align*} (x;a)_{K}=\prod_{k=0}^{K-1}(1-a^kx)=\sum_{j=0}^K\binom{K}{j}_qa^{\binom{j}{2}}(-x)^j\tag{1} \end{align*} Here we denote with $\binom{K}{j}_q$ the q-binomial coefficient, a generalisation of the binomial coefficients.

We obtain from the product representation in (1) \begin{align*} (xa^{-K};a)_K&=\prod_{k=0}^{K-1}(1-a^{k-K}x) =\prod_{k=0}^{K-1}(1-a^{-k-1}x)\tag{2}\\ &=\prod_{k=1}^{K}(1-a^{-k}x)=\prod_{k=-K}^{-1}(1-a^kx)\tag{3} \end{align*}

Comment:

• In (2) we revert the order of the terms of the product: $k\to K-1-k$.

• In (3) we shift the index $k$ by one and replace the index $k$ with $-k$.

Putting (1) and (3) together we derive the following representation of $f_K(x)$ \begin{align*} \color{blue}{f_K(x)}&=\prod_{k=-K}^{-1}(1-a^kx)\cdot\prod_{k=0}^{K}(1-a^kx)\\ &=(xa^{-K};a)_K\cdot(x;a)_{K+1}\\ &=\left(\sum_{j=0}^K\binom{K}{j}_qa^{\binom{j}{2}}(-xa^{-K})^j\right)\cdot\left(\sum_{l=0}^{K+1}\binom{K+1}{l}_qa^{\binom{l}{2}}(-x)^l\right)\\ &\color{blue}{ =\sum_{n=0}^{2K+1}\left(\sum_{{{j+l=n}\atop{0\leq j\leq K}}\atop{\ \ \,0\leq l\leq K+1}}\binom{K}{j}_q\binom{K+1}{l}_q(-1)^{j+l}a^{-Kj+\binom{j}{2}+\binom{l}{2}}\right)x^n} \end{align*}