0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .