1
$\begingroup$

In the post Sum of combinations of n taken k where k is from n to (n/2)+1, it has been explained clearly how to calculate the summation of combinations from n/2 to n. I was wondering if there is any such formula for calculating the summation of odd/even combinations if n is even/odd.

For example,
Formula for summation of all possible combinations of n = 2^n

Suppose, if n is odd,
Summation of odd combinations = summation of even combinations = 2^(n-1).

How to calculate the summation of even or odd combinations if n is even? I am trying to come up with some kind of formula but couldn't. Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Hint: Using the binomial theorem, you have:

$$2^n = (1+1)^n = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k} = \sum_{\substack{k = 0 \\ k \ \text{is even}}}^{n}\dbinom{n}{k} + \sum_{\substack{k = 0 \\ k \ \text{is odd}}}^{n}\dbinom{n}{k}$$

$$0 = (1-1)^n = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}(-1)^k = \sum_{\substack{k = 0 \\ k \ \text{is even}}}^{n}\dbinom{n}{k} - \sum_{\substack{k = 0 \\ k \ \text{is odd}}}^{n}\dbinom{n}{k}$$

Now, you just have to solve for $\displaystyle\sum_{\substack{k = 0 \\ k \ \text{is even}}}^{n}\dbinom{n}{k}$ and $\displaystyle\sum_{\substack{k = 0 \\ k \ \text{is odd}}}^{n}\dbinom{n}{k}$

$\endgroup$
0
$\begingroup$

Hint: You can split into two cases according to whether a fixed element is in the combination or not, and thus reduce even/odd counting formulas for even $n$ to formulas for the case of odd $n-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.