Intereting Posts

Different ways finding the derivative of $\sin$ and $\cos$.
Proof that derivative of a function at a point is the slope of the tangent at the point
Applying Extended Euclidean Algorithm for Galois Field to Find Multiplicative Inverse
taking the limit of $f(x)$, questions
Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive
Determinant of transpose?
How to verify this limit?
Least rational prime which is composite in $\mathbb{Z}$?
Finding $\pi$ factorial
Minimum Modulus Principle for a constant fuction in a simple closed curve
Is this proof for Theorem 16.4 Munkers Topology correct?
Relation of the kernels of one bounded operator and its extension
find examples of two series $\sum a_n$ and $\sum b_n$ both of which diverge but for which $\sum \min(a_n, b_n)$ converges
Show that the following is a metric on $\mathbb R$
Find trace of linear operator

I got stuck at the computation of the sum

$$

\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}.

$$

I think there is no purely combinatorial proof here since the sum can achieve negative values. Could you give me solution, it seems to involve generating functions.

- Ways of merging two incomparable sorted lists of elements keeping their relative ordering
- $\sum_{k=0}^n (-1)^k \binom{n}{k}^2$ and $\sum_{k=0}^n k \binom{n}{k}^2$
- How do we show the equality of these two summations?
- Proof related to Fibonacci sequence
- Enumerating Graphs with Self-Loops
- How many ways can $b$ balls be distributed in $c$ containers with no more than $n$ balls in any given container?
- Probability of having $k$ similar elements in two subsets.
- How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes?
- Number of ways to write n as a sum of k nonnegative integers
- Sum of products of binomial coefficients: $ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $

Indeed, generating function method works. Let $c_n$ denoe the given sum. Then we have

$$\begin{align*}

\sum_{n=0}^{\infty} c_n y^{2n}

&= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \frac{(-1)^k y^{2n}}{(2n-2k)!k!} \int_{0}^{\infty} x^{2n-k} e^{-x} \; dx \\

&= \int_{0}^{\infty} \sum_{k=0}^{n} \sum_{n=0}^{\infty} \frac{(yx)^{2n-2k}}{(2n-2k)!} \frac{(-y^2 x)^k}{k!} e^{-x} \; dx \\

&= \int_{0}^{\infty} \cosh(yx) e^{-(y^2+1)x} \; dx \\

&= \int_{0}^{\infty} \frac{1}{2} \left( e^{-(y^2-y+1)x} + e^{-(y^2+y+1)x} \right) \; dx \\

&= \frac{1}{2} \left( \frac{1}{y^2 – y + 1} + \frac{1}{y^2 + y + 1} \right) \\

&= \frac{1 – y^4}{1 – y^6} \\

&= 1 – y^4 + y^6 – y^{10} + \cdots.

\end{align*}$$

Thus by comparing the coefficients, we have

$$ c_n = \begin{cases}

1 & n \equiv 0 \ (\mathrm{mod} \ 3) \\

0 & n \equiv 1 \ (\mathrm{mod} \ 3) \\

-1 & n \equiv 2 \ (\mathrm{mod} \ 3)

\end{cases}.$$

Similar calculation also shows that

$$ \sum_{k=0}^{n} \binom{2n-k}{k} = F_{2n+1},$$

where $F_0 = 0, F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$ is the Fibonacci sequence.

Okay, here is a direct approach, motivated by Brain M. Scott’s illuminating answer. By Pascal’s triangle,

$$\begin{align*}

c_{n+1}

&= \sum_{k=0}^{n+1}(-1)^k \binom{2n+2-k}{k} \\

&= \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k-1} + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} \\

&= – \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k} + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} \\

&= – c_n + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k}.

\end{align*}$$

But applying exactly the same technique to the last sum, we have

$$\begin{align*}

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

&= \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k-1} + \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k} \\

&= – \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k} + \sum_{k=0}^{n}(-1)^k \binom{2n-k}{k} \\

&= – \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k} + c_n.

\end{align*}$$

Plugging back, we obtain

$$ c_{n+1} = – \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k}.$$

Thus we have

$$c_{n+1}

= – c_n + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k}

= – c_n – c_{n+2},$$

or equivalently

$$c_{n+2} + c_{n+1} + c_n = 0.$$

So we have $c_{n+3} = c_n$ and the proof is complete.

This is not going to be a nice answer. Rather, it will illustrate how one might attack the problem from scratch, without using anything especially sophisticated.

Let $$a_n=\sum_{k=0}^n(-1)^n\binom{2n-k}k\;.$$

From Pascal’s triangle we have

$$\begin{align*}

\binom{2(n+1)-k}k&=\binom{2n+1-k}{k-1}+\binom{2n+1-k}k\\

&=\binom{2n-k}{k-2}+2\binom{2n-k}{k-1}+\binom{2n-k}k\;,

\end{align*}$$

so $$\begin{align*}

\sum_{k=0}^{n+1}(-1)^k\binom{2(n+1)-k}k&=\sum_{k=0}^{n+1}(-1)^k\left(\binom{2n-k}{k-2}+2\binom{2n-k}{k-1}+\binom{2n-k}k\right)\\

&=\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}{k-2}+2\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}{k-1}+\\

&\qquad\qquad+\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}k\\

&=\sum_{k=0}^{n-1}(-1)^k\binom{2(n-1)-k}k-2\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k+\\

&\qquad\qquad+\sum_{k=0}^n(-1)^k\binom{2n-k}k\;,

\end{align*}$$

or $$a_{n+1}=a_{n-1}+a_n-2\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k\;.\tag{0}$$

If we could get a handle on the summation on the righthand side, we’d be in business. Now

$$\begin{align*}

\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k&=\sum_{k=0}^{n-1}(-1)^k\left(\binom{2(n-1)-k}k+\binom{2(n-1)-k}{k-1}\right)\\

&=\sum_{k=0}^{n-1}(-1)^k\binom{2(n-1)-k}k-\sum_{k=0}^{n-2}(-1)^k\binom{2(n-1)-1-k}k\\

&=a_{n-1}-\sum_{k=0}^{n-2}(-1)^k\binom{2(n-1)-1-k}k\;,\tag{1}

\end{align*}$$

where the summation on the righthand side is just like the one on the lefthand side, but with $n$ replaced by $n-1$. That suggests that we should let $$b_n=\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k$$ and write $(1)$ as $$b_n=a_{n-1}-b_{n-1}\;.$$ Since $b_0=0$, this boils down to $$b_n=\sum_{k=0}^{n-1}(-1)^{n-1-k}a_k\;,$$ while $(0)$ can be rewritten as $$a_{n+1}=a_n+a_{n-1}-2b_n=a_n-a_{n-1}+2\sum_{k=0}^{n-2}(-1)^{n-k}a_k\;.$$

In particular, $$a_{n+3}=a_{n+2}-a_{n+1}+2\sum_{k=0}^n(-1)^{n-k}a_k\;,\tag{2}$$ and you know that $a_0=1,a_1=0,a_2=-1$, and the sequence seems to repeat with a period of $3$. Can you now use $(2)$ to show by induction that this is actually the case?

Specifically, you’ll want to show by simultaneous induction that

$$a_n=\begin{cases}

1,&\text{if }n\equiv 0\pmod 3\\

0,&\text{if }n\equiv 1\pmod 3\\

-1,&\text{if }n\equiv 2\pmod 3\;,

\end{cases}$$ and $$b_n=\begin{cases}

1,&\text{if }n\equiv 0\pmod 3\\

-1,&\text{if }n\equiv 1\pmod 3\\

0,&\text{if }n\equiv 2\pmod 3\;.

\end{cases}$$

There is a combinatorial proof.

First, $\binom{2n-k}{k}$ is the number of ways to tile a line board of $2n$ cells with $k$ dominoes and $2n-2k$ squares. (Dominoes take up two cells, and squares take up one.) This is because you have $2n-k$ total tiles in such a tiling, and there are $\binom{2n-k}{k}$ ways to choose which ones are dominoes.

Thus $$\sum_{k=0}^n \binom{2n-k}{k} (-1)^k$$ is the difference in the number of tilings of a $2n$-board that use an *even* number of dominoes and the number of tilings that use an *odd* number of dominoes.

We’ll say that a tiling is *unbreakable* at cell $k$ if a domino occupies cells $k$ and $k+1$.

From here, we’ll proceed in cases. Suppose $2n\equiv 2\pmod 3$. Given a tiling of the $2n$-board, find the first breakable cell of the form $3j+2$. There must be such a cell because the last cell is of this form. For there to be no breakable cells of the form $3i+2$ for $i < j$ the tiling must be of the form square, domino, square, domino, etc., up through cell $3j$. If cells $3j+1$ and $3j+2$ are covered by a domino, break it into two squares. If cells $3j+1$ and $3j+2$ are covered by two squares, replace them with a domino. This mapping is reversible, and it changes the parity of the number of dominoes. Thus, when $2n\equiv 2\pmod 3$ there are as many even tilings of the $2n$-board as there are odd tilings, as every tiling in this case must have at least one breakable cell of the form $3j+2$.

If $2n \not\equiv 2 \pmod 3$, then there is exactly one tiling that is unbreakable at all cells of the form $3j+2$. If $2n \equiv 0 \pmod 3$, then this is the tiling that consists of square, domino, square, domino, etc., for the entire length of the board, ending in a domino. Thus in this tiling there are $d$ dominoes and $s$ squares such that $2n = 2d+s = 3d$, since $d=s$ in this case. But if $3d = 2n$, then $2|d$, and so the leftover tiling has even parity.

If $2n \equiv 1 \pmod 3$, then the leftover tiling consists of square, domino, square, domino, etc., for the entire length of the board, ending in a square. Thus in this tiling $d+1 = s$, and so we get $2n = 2d+s = 3d+1$. This means means that $d$ cannot be divisible by $2$, and so the leftover tiling has odd parity.

Putting all three cases together we get $$ \sum_{k=0}^n \binom{2n-k}{k} (-1)^k =\begin{cases}

1,&\text{if }2n\equiv 0\pmod 3;\\

-1,&\text{if }2n\equiv 1\pmod 3;\\

0,&\text{if }2n\equiv 2\pmod 3.

\end{cases}$$

(Reference: Identity 172, pages 85-86, in Benjamin and Quinn’s *Proofs that Really Count*.)

Let

$$

a_n=\sum_{k=0}^n(-1)^k\binom{n-k}{k}

$$

Noting that

$$

\sum_{n=k}^\infty\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}\tag{1}

$$

we can compute the generating function of $a_n$:

$$

\newcommand{\cis}{\operatorname{cis}}

\begin{align}

\sum_{n=0}^\infty a_nx^n

&=\sum_{n=0}^\infty x^n\sum_{k=0}^n(-1)^k\binom{n-k}{k}\\

&=\sum_{k=0}^\infty\sum_{n=k}^\infty(-1)^kx^n\binom{n-k}{k}\\

&=\sum_{k=0}^\infty\sum_{n=0}^\infty(-1)^kx^{n+k}\binom{n}{k}\\

&=\sum_{k=0}^\infty(-1)^kx^k\frac{x^k}{(1-x)^{k+1}}\\

&=\frac{1}{1-x}\sum_{k=0}^\infty(-1)^k\left(\frac{x^2}{1-x}\right)^k\\

&=\frac{1}{1-x}\frac{1}{1+\frac{x^2}{1-x}}\\

&=\frac{1}{1-x+x^2}\\

&=\frac{1}{\alpha-\beta}\left(\frac{1}{x-\alpha}-\frac{1}{x-\beta}\right)\tag{2}

\end{align}

$$

where $\alpha$ and $\beta$ are the roots of $1-x+x^2=0$; $\alpha=\cis(\pi/3)$ and $\beta=\cis(-\pi/3)$.

Thus, the series for $(2)$ is

$$

\begin{align}

&\frac{1}{\cis(\pi/3)-\cis(-\pi/3)}\left(\frac{\cis(\pi/3)}{1-\cis(\pi/3)x}-\frac{\cis(-\pi/3)}{1-\cis(-\pi/3)x}\right)\\

&=\frac{2}{\sqrt{3}}\Im\left(\frac{\cis(\pi/3)}{1-\cis(\pi/3)x}\right)\\

&=\frac{2}{\sqrt{3}}\Im\left(\sum_{n=0}^\infty\cis((n+1)\pi/3)x^n\right)\tag{3}

\end{align}

$$

Therefore,

$$

a_n=\frac{2}{\sqrt{3}}\sin\left(\frac{n+1}{3}\pi\right)\tag{4}

$$

and the sequence requested above is

$$

a_{2n}=\frac{2}{\sqrt{3}}\sin\left(\frac{2n+1}{3}\pi\right)\tag{4}

$$

Consider the more general number $C_n$ defined as

$$

C_n = \sum_{k = 0}^{\infty} (-1)^k{n-k \choose k}

$$

where ${m \choose k} = 0$ if $k > m$. Then your numbers are $C_{2n}$ for $n = 0, 1, 2, \dots$. These numbers satisfy

$$

\begin{eqnarray}

C_n &=& \sum_{k = 0}^{\infty}(-1)^k\left( {n-1-k \choose k} + {n-1-k \choose k-1} \right)\\

&=& C_{n-1} – \sum_{k = 0}^{\infty} (-1)^k {n – 2 – k \choose k}\\

&=& C_{n-1} – C_{n-2}

\end{eqnarray}

$$

The sequence $C_0, C_1, C_2, \dotsc$ is therefore

$$

1, 1, 0, -1, -1, 0, 1, 1, 0, -1, \dotsc

$$

and taking out the even terms $C_0, C_2, C_4, \dotsc$ gives your sequence

$$

1, 0, -1, 1, 0, -1, \dotsc

$$

In other words $C_{2n} = (2 – n \mod 3) – 1$.

If you want only the result, CAS says

$$

\frac{2\sqrt{3}}{3}(\cos\left( \frac{(4n-1)\pi}{6}\right).

$$

- Prove that if n is even then $n^2$ is even and if n is odd then $n^2$ is odd?
- Is my proof correct? ($A_n$ is generated by the set of all 3-cycles for $n \geq 3$)
- Find the remainder of $\frac{2^{2014}}{7}$
- Idea behind definitions in math
- What is the cardinality of a set of all monotonic functions on a segment $$?
- How to calculate $\cos(6^\circ)$?
- Are there arbitrarily large gaps between consecutive primes?
- Can a basis for $\mathbb{R}$ be Borel?
- Collatz conjecture: Largest number in sequence with starting number n
- A continuous bijection from the Cantor Set to
- What does the term “undefined” actually mean?
- How can we factorise a general second degree expression?
- When will a parametric solution generate all possible solutions?
- Are these 2 graphs isomorphic?
- Evaluate $\int_{0}^{+\infty }{\left( \frac{x}{{{\text{e}}^{x}}-{{\text{e}}^{-x}}}-\frac{1}{2} \right)\frac{1}{{{x}^{2}}}\text{d}x}$