How do I re-index $\sum_{i=0}^t \sum_{j=0}^t \sum_{k=0}^\infty \binom{t}{i} \binom{t}{j} \binom{k+t-1}{t-1} x^{i+j+k}$

Question

How do I re-index $$\sum_{i=0}^t \sum_{j=0}^t \sum_{k=0}^\infty \binom{t}{i} \binom{t}{j} \binom{k+t-1}{t-1} x^{i+j+k}$$ to compare coefficients with $\displaystyle \sum_{n=0}^t \binom{t}{n} x^n$?

I am trying to extract the coefficient for this power series identity:

$$\frac {(1+x)^t} {(1-x^2)^t} = \frac 1 {(1-x)^t}$$

after replacing with respective binomial series, I get this triple summation but I don't understand how to re-index $i+j+k = n$ correctly to compare the coefficients of $x^n$.

Any help appreciated, thanks!

Answer 1

The derivation of the triple sum is not that clear to me, but here is an alternate calculation which might be helpful.

From the given representation \begin{align*} (1+x)^t=\sum_{n=0}^t\binom{t}{n}x^n\tag{1} \end{align*}

we compare the coefficients of the generating functions of \begin{align*} (1+x)^t=\frac{(1-x^2)^t}{(1-x)^t} \end{align*}

We obtain \begin{align*} \frac{(1-x^2)^t}{(1-x)^t}&=\left(\sum_{j=0}^\infty\binom{t}{j}(-x^2)^j\right)\left(\sum_{k=0}^\infty\binom{-t}{k}(-x)^k\right)\\ &=\sum_{n=0}^\infty\left(\sum_{{2j+k=n}\atop{j,k\geq 0}}\binom{t}{j}\binom{-t}{k}(-1)^{j+k}\right)x^n\\ &=\sum_{n=0}^\infty\left(\sum_{j=0}^n\binom{t}{j}\binom{-t}{n-2j}(-1)^{j+n}\right)x^n\tag{2}\\ &=\sum_{n=0}^\infty\left(\sum_{j=0}^n\binom{t}{j}\binom{t+n-2j-1}{t-1}(-1)^{j+n}\right)x^n\tag{3}\\ \end{align*}

Comment:

• In (2) we replace the index $k$ by $n-2j$ and use $n$ as upper limit of the inner sum by noting that $\binom{p}{q}=0$ if $0\leq p<q$.

• In (3) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

We conclude by comparing the coeffcients of $x^n$ of (1) and (3) \begin{align*} (-1)^n\binom{t}{n}=\sum_{j=0}^n(-1)^{j}\binom{t}{j}\binom{t+n-2j-1}{n-2j}\qquad\qquad 0\leq n\leq t \end{align*}

Answer 2

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\color{#f00}{\sum_{i = 0}^{t}\sum_{j = 0}^{t}\sum_{k = 0}^{\infty}{t \choose i}{t \choose j} {k + t - 1 \choose t - 1}x^{i + j + k}} = \sum_{i = 0}^{t}{t \choose i}x^{i}\sum_{j = 0}^{t}{t \choose j}x^{j} \sum_{k = 0}^{\infty}{k + t - 1 \choose k}x^{k} \\[5mm] = &\ \sum_{i = 0}^{t}{t \choose i}x^{i}\sum_{j = 0}^{t}{t \choose j}x^{j} \sum_{k = 0}^{\infty} {-\bracks{k + t - 1} + \bracks{k} - 1 \choose k}\pars{-1}^{k}x^{k} \\[5mm] = & \sum_{i = 0}^{t}{t \choose i}x^{i}\sum_{j = 0}^{t}{t \choose j}x^{j}\ \overbrace{\sum_{k = 0}^{\infty}{-t \choose k}\pars{-x}^{k}} ^{\ds{\pars{1 - x}^{-t}}} = \pars{1 - x}^{-t}\ \overbrace{\sum_{i = 0}^{t}{t \choose i}x^{i}}^{\ds{\pars{1 + x}^{t}}}\ \overbrace{\sum_{j = 0}^{t}{t \choose j}x^{j}}^{\ds{\pars{1 + x}^{t}}} = \color{#f00}{\bracks{\pars{1 + x}^{2} \over 1 - x}^{t}} \end{align}

Moreover,

\begin{align} \bracks{\pars{1 + x}^{2} \over 1 - x}^{t} & = \sum_{n = 0}^{2t}{2t \choose n}x^{n}\sum_{j = 0}^{\infty}{-t \choose j} \pars{-x}^{j} = \sum_{n = 0}^{\infty}\sum_{j = 0}^{\infty} \pars{-1}^{j}{2t \choose n}{-t \choose j}x^{n + j} \\[5mm] = &\ \sum_{j = 0}^{\infty}\sum_{n = j}^{\infty} \pars{-1}^{j}{2t \choose n - j}{-t \choose j}x^{n} = \sum_{n = 0}^{\infty} \bracks{\sum_{j = 0}^{n}\pars{-1}^{j}{2t \choose n - j}{-t \choose j}}x^{n} \end{align} such that $$ \bracks{x^{n}} \color{#f00}{\sum_{i = 0}^{t}\sum_{j = 0}^{t}\sum_{k = 0}^{\infty}{t \choose i}{t \choose j} {k + t - 1 \choose t - 1}x^{i + j + k}} = \color{#f00}{\sum_{j = 0}^{n}\pars{-1}^{j}{2t \choose n - j}{-t \choose j}} $$ CAS yields, for the last sum, an expression in terms of a Hypergeometric Function: $$ {2t \choose n}\ \mbox{}_{2}\mathrm{F}_{1}\pars{-n,t;-n + 2t + 1;-1} $$