Is this sum exponential?

1. Jul 16, 2009

twoflower

Hello,

I've been solving a problem which forces me to answer the question: "Is there a boolean function with exponential number (in variable count) of prime implicants of the length n - 1?"

Anyway, during solving this problem I came to this point:

Is the following sum exponential in $2n$?

$$\sum_{x=0}^{n} \left( \begin{array}{cc} 2n \\ 2x \end{array} \right)$$

Are there some nice combinatorial identities which I overlooked that can be useful in this case?

Thank you very much.

2. Jul 16, 2009

mathman

If you leave out the 2's in the combinatorial symbol, the answer (as you probably know) is 2n. I would guess your sum is something like 2(2n-1), since you are missing about half the terms.