# Summation of the sum into a double summation

I've been thinking about the following question which I haven't found that in any book I've researched so far. Let's consider the following summation:

$$\sum\limits_{t=0}^{n}{n \choose t} = 2^{n}$$, $$t \in \mathbb{Z+}$$

Now, let's consider that $$t = x+y$$. So we have:

$$\sum\limits_{x+y=0}^{n}{n \choose x+y}$$, with both $$x, y \in \mathbb{Z+}$$

I am interested on a way to rewrite the summation in $$t$$ as something like: $$\sum\limits_{x}\sum\limits_{y}f(x)g(y)$$, by knowing only that $$t=x+y$$. Do you have any ideas for that? I've tried something similar to a Vandermonde's identity but I could not use that in this case.

## 1 Answer

You can think combinatorially. For example, from the set {1,2,3,...,8}, ways of choosing $$k$$ elements is $$\sum \limits_{k=0}^{8} {8 \choose k}$$.

Now you can partition the set into two disjoint subsets of 4 odd and 4 even numbers. Then this sum is same as the number of ways of choosing $$i$$ odd and $$k-i$$ even elements : $$\sum \limits_{k=0}^{8} \sum \limits_{i=0}^{k} {4 \choose i} {4 \choose k-i}$$ .

PS - I'm taking $${m \choose n} = 0$$ whenever $$n > m$$.