how to compute $\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} {n \choose 2k}$?

Question

so I was solving this probability question :

We consider a set with n people, who are each assigned, one by one, either a red or a blue hat uniformly at random. These choices are independent - the choice of the hat for one person is not affected by the choice of a hat for another person.

a) What is the probability that an even number of red hats are assigned? (As a function of n.)

so the number of red hats assigned is a random variable $X \sim B(n, \frac12)$

meaning the probability that an even number of red hats are assigned is $$ \sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} P(X=2 k) = \frac{1}{2^n} \sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} {n \choose 2k} $$

however I'm not sure whether or not the answer can be simplified even further.

Answer 1

Assume that after n-1 people are assign with hat and the probability that odd number of red hat has been assigned is p so that the number of even number of red hat has been assigned is 1-p.

After assigned another hat with 1/2 probability to be red, the probability that even number of red hat has been assigned is P(hat n is red)p+P(hat n is blue)(1-p) = 1/2*p+1/2*(1-p)=1/2.

So the probability that even number of red hat has been assigned is 1/2.

Or $\frac1{2^n}\sum_{k=0}^{\lfloor{\frac n2}\rfloor}{n \choose 2k}=\frac12$

Answer 2

Also $0$ is an even number so you should start with $k=0$.

And yes, there is a simplification: $$\cdots=\frac1{2^n}2^{n-1}=\frac12$$

Have a look at the triangle of Pascal and you will see that this is immediate if $n$ is odd.

Can you prove it yourself for even $n$?

Hint to solve the question directly (inspired by the answer of Zhaohui Du):

the last hat that is assigned is decisive if it comes to odd or even.