# 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}$

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!

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*}

• wow, it seems i complicated the problem for nothing, thank you for this short and beautiful answer! – booya Sep 23 '16 at 15:12
• @booya: You're welcome! Good to see the answer is useful. :-) – Markus Scheuer Sep 23 '16 at 15:47

$\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}$$