# Calculate closed form for summation involving binomial coefficients

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}) .$$

• Welcome to MathSE. Please show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are having. Commented Jun 28, 2021 at 9:55
• I do not understand why this question has been closed. I am voting to reopen since the author has shown his attempt and explained where he is stuck. Commented Jun 28, 2021 at 10:43

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)$$.
You are correct in the analysis that $$6^n$$ is the way to divide them in $$6$$ groups. Now you have to take out the ways in which you had even ones, so you know that $$6^n-\left (\sum _{k\text{ even }}\binom{n}{k}5^{n-k}\right )=\sum _{k\text{ odd }}\binom{n}{k}5^{n-k},$$ now add both sides with the odd one again to get $$6^n-\left (\sum _{k\text{ even }}\binom{n}{k}5^{n-k}\right )+\left (\sum _{k\text{ odd }}\binom{n}{k}5^{n-k}\right )=2\sum _{k\text{ odd }}\binom{n}{k}5^{n-k}.$$ Take the last equality and associate the two sums as $$6^n-\left (\sum _{k\text{ even }}\binom{n}{k}5^{n-k}-\sum _{k\text{ odd }}\binom{n}{k}5^{n-k}\right )=2\sum _{k\text{ odd }}\binom{n}{k}5^{n-k}.$$ Hint: Notice that there is a $$-1$$ on the odd $$k$$ and so $$(-1)^k=-1$$, on the $$k$$ even case you have that $$(-1)^k=1$$. You will get the two sums with exactly the same argument. Can you finish the argument? Can you place it in a general form? Replace $$5$$ by an $$x$$.