The question is to calculate a closed formula for the amount below.
$$
\sum\limits_{\substack k = 1\\k \text{ odd}}^n \binom{n}{k}5^{n – k} .
$$
I thought to use $(1+5)^n$ (the binomial theorem of Newton) or divided into six groups.
It is equivalent to the problem of dividing $n$ students into $6$ groups with no limitation on each group such that the first group contains an odd number of students.
So in one hand, the solution is to divide into cases by $k$:
-choose the number of student that will go to the first group.$$\binom{n}{k}$$
-then divide the other to the other five groups.$$5^{n – k}$$
I'm trying to figure what will be the solution on the other hand.
I also tried to approach it binomially, but I don't know how to sum the cases over odd cases. It looks like symmetry but the odd sum is not necessary equal to the even one.
I know that to divide the $n$ students to six groups is $$6^{n}$$
I know also the final answer is
$$
\sum\limits_{\substack k = 1\\k \text{ odd}}^n \binom{n}{k}5^{n – k}=\frac{1}{2}(6^{n}-4^{n}) .
$$
Best Answer
The following useful function is $1$ when $k$ is odd, and $0$ when $k$ is even: $$ \frac{1-(-1)^k}{2} $$ Therefore, $$ \sum_{k\text{ odd}}\binom{n}k5^k=\sum_{k=0}^n\binom{n}k5^k\cdot \frac{1-(-1)^k}{2} $$ Now, expand that last sum into two sums by distributing the $\frac{1-(-1)^k}{2}$, then apply the binomial theorem to each sum. Done!
I cannot resist posting the following combinatorial solution. As you noted, $6^n$ is the number of ways to divide the $n$ students into $6$ groups numbered $1$ to $6$. Therefore, $6^n-4^n$ is the number of ways to divide students into six groups, such that not all of the students go in the first four groups. So, $6^n-4^n$ is the number of ways where there is at least one student in group $5$ or $6$.
I claim that in exactly half of the assignments counted by $6^n-4^n$, group number $6$ has an odd number of students. Indeed, consider the following transformation defined on group assignments; proceed through the $n$ students from $1$ to $n$, and for the first student who is in group $5$ or $6$, move them to the other group ($6$ or $5$). This operation is always possible, since we assumed either group $5$ or $6$ is nonempty. Furthermore, this operation always changes the parity of the size of group $6$. Therefore, the operation divides the $6^n-4^n$ assignments into pairs where exactly one assignment in each pair has group $6$ odd, so the number of assignments where group $6$ is odd is $\frac12 (6^n-4^n)$.