sum of binomial series with alternate terms

Question

Evaluation of series $\displaystyle \sum^{n}_{k=0}(-4)^k\binom{n+k}{2k}$

what I tried:

from Binomial Identity

$$\binom{n+k}{2k}=\binom{n+k-1}{2k}+\binom{n+k-1}{2k-1}$$

series is $$\sum^{n}_{k=0}(-4)^k\binom{n+k-1}{2k}+\sum^{n}_{k=0}(-4)^k\binom{n+k-1}{2k-1}$$

let $\displaystyle S_{1}=\sum^{n}_{k=0}\binom{n+k-1}{2k}=\binom{n-1}{0}-4\binom{n}{2}+4^2\binom{n+1}{4}+\cdots +(-4)^n\binom{2n-1}{2n}$

let $\displaystyle S_{2}=\sum^{n}_{k=0}\binom{n+k-1}{2k}=\binom{n-1}{-1}-4\binom{n}{1}+4^2\binom{n+1}{3}+\cdots +(-4)^n\binom{2n-1}{2n-1}$

Help me please

did not know to simplify $S_{1}$ and $S_{2}$

Answer 1

I couldn't see a slick way to do this, but I computed a few terms and guessed that the sum is $(-1)^n(2n+1).$ In trying to prove this by induction, I ran into the sum $\sum_{k=0}^n(-4)^k\binom{n+k}{2k-1}$, just as you did. Again, I did experiments, and guessed the sum. This led me to the proposition

Let $$S_n=\sum_{k=0}^n(-4)^k\binom{n+k}{2k}\\ T_n=\sum_{k=0}^n(-4)^k\binom{n+k}{2k-1}$$ Then $$\begin{align} S_n&=(-1)^n(2n+1)\\ T_n&=(-1)^n(4^{n+1}-4n-4) \end{align}$$

This is easily proved by induction, provided you prove both formulas at once. That is, show they are both true for $n=1$, assume they are both true for some $n$, and then prove they both hold for $n+1$.

Answer 2

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}\color{blue}{(-4)^k\binom{n+k}{2k}}&=\sum_{k=0}^n(-4)^k\binom{n+k}{n-k}\\ &=\sum_{k=0}^n(-4)^k[z^{n-k}](1+z)^{n+k}\tag{2}\\ &=[z^n](1+z)^n\sum_{k=0}^n(-4z(1+z))^k\tag{3}\\ &=[z^n](1+z)^n\frac{1-(-4z(1+z))^{n+1}}{1+4z(1+z)}\tag{4}\\ &=[z^n](1+z)^n\frac{1}{1+4z(1+z)}\tag{5}\\ &=[z^n]\frac{(1+z)^n}{(1+2z)^2}\\ &=[z^n](1+z)^n\sum_{j=0}^\infty\binom{-2}{j}(2z)^j\tag{6}\\ &=[z^n](1+z)^n\sum_{j=0}^\infty(j+1)(-2z)^j\tag{7}\\ &=\sum_{j=0}^n(j+1)(-2)^j[z^{n-j}](1+z)^n\\ &=\sum_{j=0}^n(j+1)(-2)^j\binom{n}{n-j}\tag{8}\\ &=\sum_{j=1}^n\binom{n}{j}j(-2)^j+\sum_{j=0}^n\binom{n}{j}(-2)^j\\ &=n\sum_{j=1}^n\binom{n-1}{j-1}(-2)^j+(1+(-2))^n\tag{9}\\ &=n\sum_{j=0}^{n-1}\binom{n-1}{j}(-2)^{j+1}+(-1)^n\tag{10}\\ &=(-2n)(1+(-2))^{n-1}+(-1)^n\\ &\,\,\color{blue}{=(-1)^n(2n+1)} \end{align*}

Comment:

• In (2) we apply the coefficient of operator according to (1).

• In (3) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (4) we apply the finite geometric series formula.

• In (5) we skip the term which does not contribute to $[z^n]$.

• In (6) we apply the binomial series expansion.

• In (7) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (8) we select the coefficient of $z^{n-j}$.

• In (9) we apply the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (10) we shift the index to start with $j=0$.

Answer 3

With the following the purpose was to use slightly different functions from what we saw in the answer by @MarkusScheuer. Start from

$$\sum_{k=0}^n (-4)^k {n+k\choose 2k} = \sum_{k=0}^n (-4)^k [z^{n-k}] \frac{1}{(1-z)^{2k+1}} \\ = [z^n] \frac{1}{1-z} \sum_{k=0}^n (-4)^k \frac{z^k}{(1-z)^{2k}}.$$

Here the coefficient extractor enforces the range and we get

$$[z^n] \frac{1}{1-z} \sum_{k\ge 0} (-4)^k \frac{z^k}{(1-z)^{2k}} = [z^n] \frac{1}{1-z} \frac{1}{1+4z/(1-z)^2} \\ = [z^n] \frac{1-z}{(1-z)^2+4z} = [z^n] \frac{1-z}{(1+z)^2} \\ = [z^n] \frac{1}{(1+z)^2} - [z^{n-1}] \frac{1}{(1+z)^2} \\ = (-1)^n (n+1) - (-1)^{n-1} n = (-1)^n (2n+1).$$

Answer 4

Let

$$S_n=\displaystyle \sum^{n}_{k=0}(-4)^k\binom{n+k}{2k}\tag{*}$$

This issue can be connected in a natural way to Chebyshev polynomials of the second kind, with explicit expression see Wikipedia article.

$$U_n(x)=\sum_{k=0}^n(-2)^k\binom{n+k+1}{2k+1}(1-x)^k\tag{1}$$

If we take $x=-1$ in (1),

$$U_n(-1)=\sum_{k=0}^n(-4)^k\binom{n+k+1}{2k+1}=(-1)^n (n+1),\tag{2}$$

the second expression for $U_n(-1)$ being a known property (see Remark below).

Now, let us write the same expression as (2), but for $n-1$ instead of $n$ :

$$U_{n-1}(-1)=\sum_{k=0}^{n-1}(-4)^k\binom{n+k}{2k+1}=(-1)^{n-1} (n)\tag{3}$$

Subtracting (3) from (2),

$$\sum_{k=0}^{n-1}(-4)^k\underbrace{\left(\binom{n+k+1}{2k+1}-\binom{n+k}{2k+1}\right)}_{\binom{n+k}{2k}}+(-4)^n=\underbrace{(-1)^n (n+1) - (-1)^{n-1} (n)}_{(-1)^n (2n+1)}\tag{4}$$

(we have used the classical recurrence relationship between binomial coefficients)

It is finished there because (4) expresses the fact that $S_n$ (given by (*)) is :

$$S_n=(-1)^n (2n+1)$$

Remark : Why do we have $U_n(-1)=(-1)^n (n+1)$ ?

It can be easily seen by setting $x=-1$ into the generating function of the $U_n$s :

$$\sum_{n=0}^{\infty}U_n(x)t^n=\dfrac{1}{1-2tx+t^2}$$

giving

$$\dfrac{1}{(1+t)^2}=1-2t+3t^2-4t^3+\cdots$$