Combinations series: $\frac{{n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots}{n^2(n+3)\cdot 2^n}$

Evaluate $$\frac{{n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots}{n^2(n+3)\cdot 2^n}$$ for $$n=10$$.

Attempt: I'll deal with the case n being even, as we need to evaluate for n=10.

the numerator is

$${n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots$$

$$=\sum_{r=odd} {n \choose r}(n-r)^3$$(not sure if this is a correct notation).

$$=\sum_{r=odd}{n \choose n-r}r^3=\sum_{r=odd} {n \choose r}r^3$$(parity being same as n is even and r is odd, although I don't think this matters much).

Using the identity $${n \choose r}=\frac{n}{r} {n-1 \choose r-1}$$ repeatedly in following steps,

$$=n\sum_{r=even} {n-1 \choose r-1}r^2$$

$$=[n(n-1)](1+\sum_{r=odd} {n-2 \choose r-2}[(r-2+3)+\frac{1}{r-1}]$$

$$=[n(n-1)](1+(n-2)\sum_{r=even}{n-3 \choose r-3}+3\sum_{r=odd}{n-2 \choose r-2}+\frac{1}{n-1} \sum_{r=even}{n-1 \choose r-1} -1)$$

$$=[n(n-1)]((n-2)\cdot 2^{n-4} +3\cdot 2^{n-4}+\frac{2^{n-2}}{n-1}$$

This simplfies to $$n \cdot 2^{n-4} (n^2+7n-4)$$.

Which is incorrect. The answer for $$n=10$$ (numerator/denominator is given as $$\frac{1}{16}$$).

Where am I going wrong?

Also the hint given for this problem was "expand $$\frac{(e^x+1)^n - (e^x-1)^n}{2}$$ in two different ways". I didn't quite understand this approach?

Could someone please explain this approach and any other approach also?

Following the given hint, we have that \begin{align}\sum_{r \text{ odd}} {10 \choose r}(10-r)^3&=\frac{1}{2}\left[\left((e^x+1)^{10}-(e^x-1)^{10}\right)'''\right]_{x=0}\\ &=\left[360(e^x+1)^7e^{3x}+135(e^x+1)^8e^{2x}+5(e^x+1)^9e^x\right.\\ &\quad \left.-360(e^x-1)^7e^{3x}-135(e^x-1)^8e^{2x}-5(e^x-1)^9e^x\right]_{x=0}\\ &=360\cdot 2^7+135\cdot 2^8+5\cdot 2^9. \end{align}. The same approach works for any integer $$n\geq 4$$: \begin{align}\sum_{r \text{ odd}} {n \choose r}(n-r)^3 &=\frac{1}{2}\left[\left((e^x+1)^{n}-(e^x-1)^{n}\right)'''\right]_{x=0}\\ &=3\binom{n}{3}2^{n-3}+3\binom{n}{2}2^{n-2}+n2^{n-2} =\frac{n^2(n+3)2^n}{16}. \end{align} P.S. We could also use the Taylor series of $$e^x$$: for $$n\geq 4$$ \begin{align}\frac{1}{2}\left[\left((e^x+1)^{n}-(e^x-1)^{n}\right)'''\right]_{x=0} &=\frac{3!}{2}[x^3]\left((e^x+1)^{n}-(e^x-1)^{n}\right)\\ &=3[x^3]\left(2+x+\frac{x^2}{2}+\frac{x^3}{6}\right)^{n}\\ &=3[x^3]n2^{n-1}\left(x+\frac{x^2}{2}+\frac{x^3}{6}\right)\\ &\quad +3[x^3]\binom{n}{2}2^{n-2}\left(x+\frac{x^2}{2}+\frac{x^3}{6}\right)^2\\ &\quad +3[x^3]\binom{n}{3}2^{n-3}\left(x+\frac{x^2}{2}+\frac{x^3}{6}\right)^3\\ &=n2^{n-2}+3\binom{n}{2}2^{n-2}+3\binom{n}{3}2^{n-3}\\ &=\frac{n^2(n+3)2^n}{16}. \end{align}

Here's an alternative approach that does not depend on the hint. Because $$\frac{1+(-1)^k}{2}=\begin{cases}1&\text{if k is even}\\0&\text{if k is odd}\end{cases}$$ we have $$\sum_{k\ge 0} a_{2k} = \sum_{k\ge 0} a_k \frac{1+(-1)^k}{2}.$$ Now take $$a_k=\binom{n}{k+1}(k+1)^3$$ to obtain \begin{align} &\sum_{k\ge 0} \binom{n}{2k+1}(2k+1)^3 \\ &= \sum_{k\ge 0} \binom{n}{k+1}(k+1)^3 \frac{1+(-1)^k}{2} \\ &= \sum_{k\ge 0} \frac{n}{k+1}\binom{n-1}{k}(k+1)^3 \frac{1+(-1)^k}{2} \\ &= n\sum_{k\ge 0} \binom{n-1}{k}(k+1)^2 \frac{1+(-1)^k}{2} \\ &= n\sum_{k\ge 0} \binom{n-1}{k}\left(2\binom{k}{2}+3k+1\right) \frac{1+(-1)^k}{2} \\ &= n\sum_{k\ge 0} \left(2\binom{n-1}{2}\binom{n-3}{k-2}+3(n-1)\binom{n-2}{k-1}+\binom{n-1}{k}\right) \frac{1+(-1)^k}{2} \\ &= \frac{n}{2}\left(2\binom{n-1}{2}\sum_{k\ge 0}\binom{n-3}{k-2}+3(n-1)\sum_{k\ge 0}\binom{n-2}{k-1}+\sum_{k\ge 0}\binom{n-1}{k}\right) \\ &+ \frac{n}{2}\left(2\binom{n-1}{2}\sum_{k\ge 0} \binom{n-3}{k-2}(-1)^k+3(n-1)\sum_{k\ge 0} \binom{n-2}{k-1}(-1)^k+\sum_{k\ge 0} \binom{n-1}{k}(-1)^k\right) \\ &= \frac{n}{2}\left(2\binom{n-1}{2}2^{n-3}+3(n-1)2^{n-2}+2^{n-1}\right) \\ &+ \frac{n}{2}\left(2\binom{n-1}{2}(1-1)^{n-3}+3(n-1)(1-1)^{n-2}+(1-1)^{n-1}\right) \\ &= 2^{n-4} n \left(2\binom{n-1}{2}+6(n-1)+4\right) \\ &+ \frac{n}{2}\left(2\binom{n-1}{2}[n=3]+3(n-1)[n=2]+[n=1]\right) \\ &= 2^{n-4} n^2 (n+3) + 3[n=3]+3[n=2]+\frac{1}{2}[n=1] \end{align} So the fraction for even $$n \ge 4$$ is $$\frac{2^{n-4} n^2 (n+3)}{2^n n^2 (n+3)} = \frac{1}{16}.$$

• Nice job! (+1). Jun 7, 2020 at 18:54

A quick note on notation: you can use the notation I've used in this answer, or alternatively just use regular notation and $$2r$$ / $$2r+1$$ to denote even and odd, such as $$\sum_{r \in \mathbb Z} \binom{n}{2r+1} (n-(2r+1))^3$$

Your derivation for even $$n$$ seems pretty much correct; the only issue I can see is that $$\sum_{\text{r odd}} \binom{n-2}{r-2} = 2^{n-3},$$ and you seem to have incorrectly used $$2^{n-4}$$; carrying through this correction yields the correct answer of $$\frac 1 {16}$$ for the $$n = 10$$ case. Your formula $$\binom{n}{r} = \frac n r \binom{n-1}{r-1}$$ of course breaks down when $$r = 0$$, but this doesn't actually end up being an issue here because those terms reduce to $$0$$ anyway (in general make sure you pay attention to this possibility though).

Of course this will yield a solution if you do it for $$n$$ odd as well, but the solution suggested by the hint is perhaps cleaner. With regards to that, here's a hint hint: there are two natural ways to expand the expression they give, one of which uses the formula $$x^n - y^n = (x - y) \left(x^{n-1} + x^{n-2} y + \ldots + y^{n-1}\right),$$ and the other of which uses the binomial expansion on each of the two terms $$(e^x + 1)^n$$ and $$(e^x - 1)^n$$. This second will yield something that can quite clearly be transformed into the expression you want to evaluate; transforming the first as well should then give you a solution.

• Thanks a lot! That was a really silly mistake by me ;) Jun 8, 2020 at 1:00

$$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$$ \begin{align} \sum_{{\large r = 1} \atop {\large r\ \mrm{odd}}}^{n}{n \choose r} \pars{n - r}^{3} & = \sum_{r = 0}^{n}{n \choose 2r + 1} \bracks{\pars{n - \pars{2r + 1}}}^{\, 3} \\[5mm] & = \sum_{r = 0}^{n}{n \choose r} \pars{n - r}^{\, 3}\,{1 - \pars{-1}^{r} \over 2} \\[5mm] & = \sum_{r = 0}^{n}{n \choose r}r^{\, 3}\,{1 - \pars{-1}^{\pars{n - r}} \over 2} \\[5mm] & = \sum_{r = 0}^{n}{n \choose r}{1 - \pars{-1}^{\pars{n - r}} \over 2} \bracks{z^{3}}3!\expo{rz} \\[5mm] & = 3\bracks{z^{3}}\sum_{r = 0}^{n}{n \choose r}\pars{\expo{z}}^{r} - 3\pars{-1}^{n}\bracks{z^{3}}\sum_{r = 0}^{n}{n \choose r} \pars{-\expo{z}}^{r} \\[5mm] & = 3\bracks{z^{3}}\pars{1 + \expo{z}}^{n} - 3\pars{-1}^{n}\bracks{z^{3}}\pars{1 - \expo{z}}^{n} \\[5mm] & = \color{red}{\large 1 \over 16}\,2^{n}\,n^{2}\pars{n + 3} - 3\pars{-1}^{n}\bracks{z^{3}}\pars{1 - \expo{z}}^{n}\bracks{n \leq 3} \end{align}

\begin{align} &\bbox[10px,#ffd]{3\bracks{z^{3}}\pars{1 + \expo{z}}^{n}} = 3 \times 2^{n}\bracks{z^{3}}\pars{1 + {\expo{z} - 1 \over 2}}^{n} \\[5mm] = &\ 3 \times 2^{n}\bracks{z^{3}}\pars{1 + {1 \over 2}\,z + {1 \over 4}\,z^{2} + {1 \over 12}\,z^{3}}^{n} \\[5mm] = &\ 3 \times 2^{n}\bracks{{1 \over 12}\,n + {n\pars{n - 1} \over 2}\, {1 \over 4} + {n\pars{n - 1}\pars{n - 2} \over 6}\,{1 \over 8}} = \color{red}{\large 1 \over 16}\,2^{n}\,n^{2}\pars{n + 3} \end{align}

I'm writing this answer for any arbitrary natural $$n\geq3$$ using successive differentiation of $$(1+x)^n$$.

Rewriting the numerator of given series

When $$n$$ is odd:

\displaystyle \require{cancel} \begin{align}{{n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots}&=\;^nC_1(n-1)^3+\: ^nC_3(n-3)^3+ \ldots +\: ^nC_{n-2}(n-(n-2))^3 +\:\cancelto{0}{^nC_n (n-n)^3}\\ &= \; ^nC_2 \: 2^3 + \: ^nC_4 \: 4^3+ \ldots + \: ^nC_{n-3} (n-3)^3+ \: ^nC_{n-1} (n-1)^3\\ &= \sum_{r \; even} \: ^nC_r \: r^3 \text{ \; (say)} \end{align}

When $$n$$ is even:

\displaystyle \begin{align}{{n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots}&=\;^nC_1(n-1)^3+\: ^nC_3(n-3)^3+ \ldots +\: ^nC_{n-3}(n-(n-3))^3 +\:{^nC_{n-1} (n-(n-1))^3}\\ &= \; ^nC_1 \: 1^3 + \: ^nC_3 \: 3^3+ \ldots + \: ^nC_{n-3} (n-3)^3+ \: ^nC_{n-1} (n-1)^3\\ &= \sum_{r \; odd} \: ^nC_r \: r^3 \text{ \; (say)} \end{align}

Now, for any $$n \geq 3$$, we have

\displaystyle \begin{align}(1+x)^n&=1+\:^nC_1\:x+\:^nC_2 \:x^2+\ldots + x^n\\ n(1+x)^{n-1}&= \:^nC_1+\:2\;^nC_2 \:x+\ldots + nx^{n-1} \text{\; (Differentiated above w.r.t x)}\\ nx(1+x)^{n-1}&= \:^nC_1 \: x+\:2\;^nC_2 \:x^2+\ldots + nx^{n}\\ n(1+x)^{n-1}+ n(n-1)x(1+x)^{n-2}&= \:^nC_1+\:2^2\;^nC_2 \:x+\ldots + n^2x^{n-1} \text{\; (Differentiated above w.r.t x)}\\ nx(1+x)^{n-1}+ n(n-1)x^2(1+x)^{n-2}&= \:^nC_1\: x+\:2^2\;^nC_2 \:x^2+\ldots + n^2x^{n}\\ n(1+x)^{n-1}+ n(n-1)x(1+x)^{n-2}+2n(n-1)x(1+x)^{n-2}+n(n-1)(n-2)x^2(1+x)^{n-3}&= \:^nC_1+\:2^3\;^nC_2 \:x+\ldots + n^3x^{n-1} \text{\; (Differentiated above w.r.t x)}\\ nx(1+x)^{n-1}+ 3n(n-1)x^2(1+x)^{n-2}+n(n-1)(n-2)x^3(1+x)^{n-3}&= \:^nC_1 \: x+\:2^3\;^nC_2 \:x^2+\ldots + n^3x^{n}=S(x) \text{ \; (say)} \tag{i} \end{align}

Hence, when $$n$$ is odd

\displaystyle \begin{align}S(1)&=\quad ^nC_1 \: +\:2^3\;^nC_2 + \: 3^3 \; ^nC_3+ \ldots +(n-1)^3\;^nC_{n-1}+ n^3\; ^nC_n\\ S(-1)&=-\;^nC_1+\:2^3\;^nC_2 - \: 3^3 \; ^nC_3+\ldots +(n-1)^3\;^nC_{n-1}-n^3\; ^nC_n\\ \hline S(1)+S(-1)&=2\:(2^3 \:^nC_2 + 4^3 \: ^nC_4+\ldots+(n-3)^3\: ^nC_{n-3}+(n-1)^3\: ^nC_{n-1}\\ \frac{S(1)}2&=\sum_{r \; even} \: ^nC_r \: r^3 \quad (\because S(-1)=0 \: \forall n \in \Bbb N\;\text{ from equation (i)})\end{align}

Similarly, when $$n$$ is even \displaystyle \begin{align}S(1)&=\quad ^nC_1 \: +\:2^3\;^nC_2 + \: 3^3 \; ^nC_3+ \ldots +(n-1)^3\;^nC_{n-1}+ n^3\; ^nC_n\\ S(-1)&=-\;^nC_1+\:2^3\;^nC_2 - \: 3^3 \; ^nC_3+\ldots -(n-1)^3\;^nC_{n-1}+n^3\; ^nC_n\\ \hline S(1)-S(-1)&=2\:(\:^nC_1 + 3^3 \: ^nC_3+\ldots+(n-3)^3\: ^nC_{n-3}+(n-1)^3\: ^nC_{n-1}\\ \frac{S(1)}2&=\sum_{r \; odd} \: ^nC_r \: r^3 \quad (\because S(-1)=0 \: \forall n \in \Bbb N\;\text{ from equation (i)})\end{align}

Therefore, for any $$n\geq 3$$:

\displaystyle \begin{align} {{n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots}&=\frac{S(1)}{2} \text{ (since S(1) is same for both even n and odd n)} \\ &={{n2^{n-1}+3n(n-1)2^{n-2}+n(n-1)(n-2)2^{n-3}}\over 2}\; (\text{from equation (i)})\\ &={n2^{n-2}+3\:^nC_2\:2^{n-2}+3\:^nC_3\:2^{n-3}}\\ \implies \frac{{n \choose 1}(n-1)^3+{n \choose 3}(n-3)^3+\ldots}{n^2(n+3)\cdot 2^n} &={2n+6\:^nC_2+3\:^nC_3\over 8n^2(n+3)}\end{align}

For $$n=10$$, the above identity can be verified.