2
$\begingroup$

Find $\frac{{n\choose 1}(n-1)^3+{n\choose 3}(n-3)^3+...}{n^2(n+3)2^n}$

My attempt at this question was to first write the numerator as $\sum_{k=1}^{n} {n\choose 2k-1}(n-(2k-1))^3$ and then expanding this we would get expression like $\sum_{k=1}^{n} {n\choose 2k-1}(2k-1)^3$ which if I write as $\frac{1}{2}\sum_{r=0}^{n}{n\choose r}r^3$ I might be able to solve this using the repeated differentiation of $(1+x)^n$ , But overall I am not sure if my approach is correct the sum seemed to get more complicated , is there any more elegant ways to solve this ?

$\endgroup$
3
  • $\begingroup$ Where does the sum end? is it to infinity? $\endgroup$
    – User688539
    Aug 21 at 6:10
  • $\begingroup$ How can it be infinity? It ends at $\{n choose n}$ or $\{n choose (n-1)}$ depending whether n is odd or even $\endgroup$ Aug 21 at 6:13
  • $\begingroup$ Soumili Nag, Since this question is closed, I've written an answer here math.stackexchange.com/a/4229619/819784 using repeated differentiation of $(1+x)^n$, also pointed by @rezhaadriantanuharja . Hope this helps. $\endgroup$ Aug 21 at 10:56
3
$\begingroup$

You have $n$ people, of these you want to select an odd number of people to be in a committee, then from the non committee you choose a technical, marketing, and sales manager where one person can have more than one title. The number of possibilities are:

$$ \sum_{i\in\mathbb{N}}{\binom{n}{2i-1}\left(n-(2i-1)\right)^{3}} $$

Which is the numerator of your equation. Now let’s count in a different way. We choose the managers first then select an odd number of people from the non managers. The following are the sum of possibilities from the case when all managers are different, one person hold two titles, and one person hold three titles:

$$ 3!\cdot\binom{n}{3}\cdot 2^{n-4}+3\cdot2\cdot\binom{n}{2}\cdot 2^{n-3}+\binom{n}{1}\cdot 2^{n-2} $$

Here I use the well known fact that there are $2^{m-1}$ odd - subset of a set with $m$ members. The two expressions are equal since both count the same possibilities, only with different method

$\endgroup$
7
  • $\begingroup$ @Rehza Adrian Tanuhajra this method is Awesome...but is there any way to do it using algebra? $\endgroup$ Aug 21 at 6:08
  • $\begingroup$ @SOUMILINAG I think algebraically your idea of differentiation of $(1+x)^{n}$ is a good idea $\endgroup$ Aug 21 at 6:13
  • $\begingroup$ @SOUMILINAG try differentiating, then multiply by $x$, then repeat 2 more times. Then substitute $x=1$ & $x=-1$, the difference is twice your numerator $\endgroup$ Aug 21 at 6:18
  • $\begingroup$ The correct way. Btw it should be possibilities not probabilities $\endgroup$
    – User688539
    Aug 21 at 6:35
  • 1
    $\begingroup$ @Buraian the 2 is because we have two people so we want to choose who has two titles, the 3 is to choose whether the lone title is technical, marketing, or sales manager $\endgroup$ Aug 21 at 7:09
2
$\begingroup$

Algebraic brute force way:

$$ S = \sum_{k=1}^n \binom{n}{2k+1} \left[ n- (2k+1) \right]^3= \sum_k \binom{n}{2k+1} \left[ \sum_j \binom{3}{j} (2k+1)^j n^{3-j}\right]= \sum_j \binom{3}{j} n^{3-j} \sum_k \binom{n}{2k+1} (2k+1)^j \tag{1}$$

We need to evaluate: $$\sum_k \binom{n}{2k+1} (2k+1)^j$$

Notice that $$x \frac{d}{dx} (1+x)^n= x\frac{d}{dx} \sum_k \binom{n}{k} x^k = \sum_k \binom{n}{k}k x^k$$

Call $\phi= x \frac{d}{dx}$ then:

$$ \phi^j \left[ (1+x)^n\right] = \sum_k \binom{n}{k} k^j x^k $$

Now, we just need to take odd part of both sides and evaluate at one, which is given as:

$$ \phi^j \left[ (1+x)^n - (1-x)^n \right]|_{x=1} = \sum_k \binom{n}{2k+1} (2k+1)^j $$

Hence (1) becomes:

$$ S= \sum_j \binom{3}{j} n^{3-j} \phi^j \left[ (1+x)^n - (1-x)^n \right]_{x=1}$$

It maybe noted that $\phi^j$ can be expanded into a linear combination of ordinary derivatives weighted by Stirling numbers. Refer


$\endgroup$
1
  • $\begingroup$ This was a mess.. but hey , it does count as an algebraic method, right? $\endgroup$
    – User688539
    Aug 21 at 6:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.