$\sum_{k=0}^n \sum_{j=0}^k { {n} \choose {j}} { {n-j} \choose {k-j}} \left( \frac{x}{1-x}\right)^k = \left( \frac{1+x}{1-x} \right)^n$

Question

How to prove the following formula? $$\sum_{k=0}^n \sum_{j=0}^k { {n} \choose {j}} { {n-j} \choose {k-j}} \left( \frac{x}{1-x}\right)^k = \left( \frac{1+x}{1-x} \right)^n$$

I have tried to write $(1+x)^n$ with binomial formula in the upstairs but I don't see how to include the downstairs into this. This formula actually arises from enumerating supports of squarefree monomials of $\mathbb{F}[x_1,\dots, x_n, y_1, \dots, y_n]$ written with multi-indeces as $x^a y^b$ such that $a \cdot b = 0$. I think it can be done with considering the simplicial complex they form as a iterated join of one that is just two points. But I'd like to prove the formula in a more "simple" way.

Answer 1

Let $ n $ be a positive integer.

\begin{aligned} \sum_{k=0}^{n}{\sum_{j=0}^{k}{\binom{n}{j}\binom{n-j}{k-j}\left(\frac{x}{1-x}\right)^{k}}}&=\sum_{j=0}^{n}{\sum_{k=j}^{n}{\binom{n}{j}\binom{n-j}{k-j}\left(\frac{x}{1-x}\right)^{k}}}\\ &=\sum_{j=0}^{n}{\binom{n}{j}\left(\frac{x}{1-x}\right)^{j}\sum_{k=0}^{n-j}{\binom{n-j}{k}\left(\frac{x}{1-x}\right)^{k}}}\\ &=\sum_{j=0}^{n}{\binom{n}{j}\left(\frac{x}{1-x}\right)^{j}\left(1+\frac{x}{1-x}\right)^{n-j}}\\ &=\left(\frac{x}{1-x}+1+\frac{x}{1-x}\right)^{n}\\ \sum_{k=0}^{n}{\sum_{j=0}^{k}{\binom{n}{j}\binom{n-j}{k-j}\left(\frac{x}{1-x}\right)^{k}}}&=\left(\frac{1+x}{1-x}\right)^{n}\end{aligned}

Answer 2

Another way to do it is to start on the righthand side:

$$\begin{align*} \left(\frac{1+x}{1-x}\right)^n&=\left(1+\frac{2x}{1-x}\right)^n\\ &=\sum_{k=0}^n\binom{n}k\left(\frac{2x}{1-x}\right)^k\\ &=\sum_{k=0}^n\binom{n}k\left(\frac{x}{1-x}\right)^k2^k\\ &=\sum_{k=0}^n\binom{n}k\left(\frac{x}{1-x}\right)^k\sum_{j=0}^k\binom{k}j\\ &=\sum_{k=0}^n\sum_{j=0}^k\binom{n}k\binom{k}j\left(\frac{x}{1-x}\right)^k. \end{align*}$$

Now use the identity

$$\binom{n}k\binom{k}j=\binom{n}j\binom{n-j}{k-j},$$

which can be proved either algebraically, expanding the binomial coefficients in terms of factorials, or combinatorially: each side yields the number of ways of partitioning $[n]=\{1,\ldots,n\}$ into sets $A$, $B$, and $C$ of cardinalities $j$, $k-j$, and $n-k$, respectively.

Answer 3

Use $${p \choose q} {q \choose r}={p \choose r} {p-r \choose q-r}$$ Then $$S=\sum_{k=0}^{n} \sum_{j=0}^k {n \choose j} {n-j \choose k-j} \left(\frac{x}{1-x}\right)^k=\sum_{k=0}^{n} {n \choose k} \left(\frac{2x}{1-x}\right)^k\sum_{j=0}^{k} {k\choose j}=\sum_{k=0}^{n} {n \choose k} \left(\frac{x}{1-x}\right)^k 2^k$$ $$\implies S=\left(1+\frac{2x}{1-x}\right)^n=\left(\frac{1+x}{1-x}\right)^n$$