# Help needed on a problem regarding diffcult manipulation of binomial coefficients

What is the coefficient of $x^{n-1}$ in $$(x+1)^{n}+(x+1)^{n+2}+(x+1)^{n+4}+\dots+(x+1)^{n+2m}\;,$$ where $x,n,m$ are positive integers? Is there a closed form answer?

-
I was just wondering if there are relationship between the coefficient of $x^{n-1}$ in $(x+1)^n+(x + 1)^{n+2}+... +(x+1)^{n+2m}$ and the coefficient of $x^{n-1}$ in $(x+1)^{n-1}+(x+1)^{n+1}+... +(x+1)^{n+2m-1}$. –  user25353 Feb 21 '12 at 18:15

By the binomial theorem the coefficient is $\sum_{i=0}^m\binom{n+2i}{n-1}$

-
Look again at the exponents: it’s actually $$\sum_{k=0}^m\binom{n+2k}{n-1}\;.$$ –  Brian M. Scott Feb 20 '12 at 22:14
Thanks, I missed that –  azarel Feb 20 '12 at 22:19
I agree, but is there a closed form? –  user25353 Feb 20 '12 at 22:42

By the binomial theorem this is

$$\sum_{k=0}^m\binom{n+2k}{n-1}=\sum_{k=0}^m\binom{n+2k}{1+2k}\;.$$

For $n=1$ this is easily seen to be $m+1$, and the case $n=2$ is almost as easy: it’s $2\binom{m+2}2$.

For $n=3$ it can be expressed as $$\frac16(m+1)(m+2)(4m+9)=4\binom{m+3}3-\binom{m+2}2\;,$$ which already looks rather unpromising.

For $n=4$ the series is $4+35+126+330+715+\dots$, yielding $4,39,165,495,1210\dots$ as the sequence of values. Since this sequence isn’t in OEIS, I’m not too sanguine about the possibility of coming up with a closed form for the general problem.

-

Hint: Coefficient of $x^k$ in $(1+x)^n$ is $\displaystyle\binom n k$. Further $\displaystyle\binom n k=\displaystyle\binom n {n-k}$

Also, you'll need this $$\binom n r +\binom n {r+1}=\binom {n+1}{r+1}$$

A simple answer would be: $$\sum_{k=0}^m\binom{n+2k}{2k+1}$$ However, a closed form evades me. For consecutive exponents, I have succeeded and I've added it below.

Here's a full solution for consecutive exponents:

The coefficient of $x^{n-1}$ is \begin{align}&\binom {n}{n-1} +\binom{n+1}{n-1} +\binom {n+2}{n-1}+ \cdots +\binom {n+2m}{n-1}\\&=n+1-1+\binom{n+1}{n-1} +\binom {n+2}{n-1}+ \cdots +\binom {n+2m}{n-1}\\&=\binom {n+1}{1}+\binom{n+1}{2} +\binom {n+2}{3}+ \cdots +\binom {n+2m}{2m+1}-1\\&=\binom {n+2m+1}{2m+1} -1\\&=\binom {n+2m+1}{n} -1\end{align}

-
True, but it’s not clear that it really helps much. –  Brian M. Scott Feb 20 '12 at 22:15
@Brrian I have edited a bit(?) recently. How does it look now? –  user21436 Feb 20 '12 at 22:24
You’ve made the same mistake that azarel originally made. The OP’s sum has only even powers of $x+1$, which makes it much harder. –  Brian M. Scott Feb 20 '12 at 22:32
The last step is slightly off: that should be $$\binom{n+2m+1}{2m+1}-1=\binom{n+2m+1}n-1\;.$$ –  Brian M. Scott Feb 20 '12 at 22:54
@Brian Thank You. Fixed! –  user21436 Feb 20 '12 at 22:57

$${n \choose n - 1} + {n + 2 \choose n - 1} + {n + 4 \choose n - 1} + {n + 6 \choose n - 1} + \dots + {n + 2(m - 1) \choose n - 1}$$ is the coefficient of $x^{n - 1}$ in $$(x + 1)^n + (x + 1)^{n + 2} + \dots + (x + 1)^{n + 2(m - 1)} = \dfrac{(x + 1)^n((x + 1)^{2m} - 1)}{(x + 1)^2 - 1} \;,$$

and $${n - 1 \choose n - 1} + {n + 1 \choose n - 1} + {n + 3 \choose n - 1} + {n + 5 \choose n - 1} + \dots + {n + 2m - 3 \choose n - 1}$$ is the coefficient of $x^{n - 1}$ in $$(x + 1)^{n - 1} + (x + 1)^{n + 1} + \dots + (x + 1)^{n + 2m - 3} = \dfrac{(x + 1)^{n - 1}((x + 1)^{2m} - 1)}{(x + 1)^2 - 1} \;.$$

Now \begin{align*}&{n \choose n - 1} - {n - 1 \choose n - 1} + {n + 2 \choose n - 1} - {n + 1 \choose n - 1} +\binom{n+4}{n-1}-\binom{n+3}{n-1}+\dots \\ &\dots + {n + 2(m - 1) \choose n - 1} - {n + 2m - 3 \choose n - 1} \end{align*} is the coefficient of $x^{n - 1}$ in \begin{align*}&\dfrac{(x + 1)^n((x + 1)^{2m} - 1)}{(x + 1)^2 - 1} - \dfrac{(x + 1)^{n - 1}((x + 1)^{2m} - 1)}{(x + 1)^2 - 1}=\\ &\dfrac{x(x + 1)^{n - 1}((x + 1)^{2m} - 1)}{(x + 1)^2 - 1}=\\ &x\Big((x + 1)^{n - 1} + (x + 1)^{n + 1} + ... + (x + 1)^{n + 2m - 3}\Big)\;, \end{align*}

which is

$${n - 1 \choose n - 2} + {n + 1 \choose n - 2} + {n + 3 \choose n - 2} + {n + 5 \choose n - 2} + \dots + {n + 2m - 3 \choose n - 2} \;.$$

So \begin{align*} &{n \choose n - 1} + {n + 2 \choose n - 1} + {n + 4 \choose n - 1} + {n + 6 \choose n - 1} + \dots + {n + 2(m - 1) \choose n - 1} =\\ &\left({n - 1 \choose n - 1} + {n + 1 \choose n - 1} + {n + 3 \choose n - 1} + {n + 5 \choose n - 1} + \dots + {n + 2m - 3 \choose n - 1}\right)+\\ &\qquad+\left({n - 1 \choose n - 2} + {n + 1 \choose n - 2} + {n + 3 \choose n - 2} + {n + 5 \choose n - 2} + \dots + {n + 2m - 3 \choose n - 2}\right)\;. \end{align*}

But $${n - 1 \choose n - 2} + {n + 1 \choose n - 2} + {n + 3 \choose n - 2} + {n + 5 \choose n - 2} + \dots + {n + 2m - 3 \choose n - 2}$$ is of the same form as $${n \choose n - 1} + {n + 2 \choose n - 1} + {n + 4 \choose n - 1} + {n + 6 \choose n - 1} + \dots + {n + 2(m - 1) \choose n - 1} \;.$$

Therefore, $${n \choose n - 1} + {n + 2 \choose n - 1} + {n + 4 \choose n - 1} + {n + 6 \choose n - 1} + \dots + {n + 2(m - 1) \choose n - 1}$$ can be written as

$$\begin{array}{c} {n - 1 \choose n - 1} & + & {n + 1 \choose n - 1} & +& {n + 3 \choose n - 1} & +& \dots &+& {n + 2m - 3 \choose n - 1}&+\\ \binom{n-2}{n-2}&+&\binom{n}{n-2}&+&\binom{n+2}{n-2}&+&\dots&+&\binom{n+2m-4}{n-2}&+\\ \vdots&&\vdots&&\vdots&&\ddots&&\vdots\\ \binom11&+&\binom31&+&\binom51&+&\dots&+&\binom{2m-1}1&+\\ \binom00&+&\binom20&+&\binom40&+&\dots&+&\binom{2m-2}0 \end{array}$$

and summed by columns.

I think this can be simplified with the fact that $${n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3} + \dots + {n \choose n} = 2^n$$ and $${n \choose 0} + {n \choose 2} + {n \choose 4} + {n \choose 6} + \dots = 2^{n - 1} \;.$$

Can someone please try simplifying this? :)

-
This is ingenious, but it’s actually possible to reach the final stage directly, using a binomial identity sometimes called parallel summation. Unfortunately, I don’t see any way to proceed beyond this point. –  Brian M. Scott Feb 22 '12 at 8:15