0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 28, 2021 at 9:55
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jun 28, 2021 at 10:43

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .