Solution: 2018 Winter Midterm - 7

Author: Michiel Smid

Question

Let $n \geq 2$ be an even integer. What does $$ \sum_{k=0}^{\left. (n-2) \middle/ 2 \right.} {{n}\choose{2k+1}} $$ count?

(a)

The number of bitstrings of length $n$.

(b)

The number of bitstrings of length $\left. (n-2) \middle/ 2 \right.$.

(c)

The number of bitstrings of length $n$ having an odd number of 0's.

(d)

The number of bitstrings of length $n$ in which the number of 0's plus the number of 1's is at most $\left. (n-1) \middle/ 2 \right.$.

Let’s explain why some are wrong and one is right

The number of bitstrings of length $n$
Pretty sure this is wrong because the equation for the number of bitstrings of length $n$ is $2^n$
The number of bitstrings of length $\frac{n-2}{2}$
Pretty sure this is wrong because the equation for the number of bitstrings of length $n$ is $2^n$
The number of bitstrings of length $n$ having an odd number of 0's.
Let's write out the first few values of $ \binom{n}{2k+1} $
- $ \binom{n}{1} $
- $ \binom{n}{3} $
- $ \binom{n}{5} $
As can be seen, the number of 0's is odd. So that's great. The reason why $k$ only reaches a total of $ \frac{n-2}{2} $ is because in the actual equation, $k$ is multiplied by 2. If we were to have $k$ possibly be $n$, then it would be $ \binom{n}{2n+1} $, which is not possible.
The number of bitstrings of length $n$ in which the number of 0's plus the number of 1's is at most $ \frac{n-1}{2} $
I'm not sure why this would be correct