Is This Sum Exponential in 2n?

[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?

<br /> \sum_{x=0}^{n} \left( \begin{array}{cc} 2n \\ 2x \end{array} \right)<br />

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

Thank you very much.

 

[mathman]

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