Closed Form Expression of sum with binomial coefficient

Question

I have the following equation which is making me problems. $$A_{n} = \sum_{k=0}^{n} \binom{n-k}{k}(-1)^{k}$$ where $n\in\mathbb{N}$. The task is to find a closed form expression for $A_{n}$. I have two questions:

1. What is a closed form expression? We never defined it in my combinatorics class and on the internet there are several different definitions.

2. How can I find a closed form expression for $A_{n}$? Looking at Pascal's triangle, I think it might have something to do with fibonacci numbers, but still I have absolutely no idea how I can approach this task.

I would appreciate any kind of help leading to the solution, as I have to hand this in within the next 2 days. Thanks a lot and have a great day.

Answer 1

Note: As @Lucian already indicated, a closed form is an expression without using sigma signs. A closed form is regarded as simpler than a non-closed form, since we do not have to iterate using indices.

Here's a calculation which derives a (simple) recurrence relation from \begin{align*} a_n=\sum_{k=0}^n\binom{n-k}{k}(-1)^k\qquad n\geq 0\tag{1} \end{align*}

and based upon the recurrence relation we obtain a closed form for $a_n$.

$$$$

We observe

\begin{align*} a_n&=\sum_{k=0}^n\binom{n-k}{k}(-1)^k\\ &=\binom{n-0}{0}(-1)^0+\sum_{k=1}^n\binom{n-k}{k}(-1)^k\tag{2}\\ &=1+\sum_{k=1}^{n-1}\left[\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\right](-1)^k\tag{3}\\ &=1+\sum_{k=1}^{n-1}\binom{n-k-1}{k}(-1)^k+\sum_{k=1}^{n-1}\binom{n-k-1}{k-1}(-1)^k\\ &=1+\sum_{k=1}^{n-1}\binom{n-k-1}{k}(-1)^k+\sum_{k=0}^{n-2}\binom{n-k-2}{k}(-1)^{k+1}\tag{4}\\ &=\sum_{k=0}^{n-1}\binom{n-k-1}{k}(-1)^k+\sum_{k=0}^{n-2}\binom{n-k-2}{k}(-1)^{k+1}\\ &=a_{n-1}-a_{n-2}\tag{5} \end{align*}

Comment:

• In (2) we separate the summand with $k=0$ as preparation for the next step
• In (3) we use the binomial identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
• In (4) we shift the index of the right hand sum by one

With (5) we have derived a recurrence relation valid for $n\geq 2$

\begin{align*} a_n=a_{n-1}-a_{n-2} \end{align*}

To fully specify the recurrence relation we also have to specify $a_0$ and $a_1$. But first let's solve the recurrence relation:

We observe by substituting $a_{n-1}$: \begin{align*} a_n=a_{n-1}-a_{n-2}=(a_{n-2}-a_{n-3})-a_{n-2}=-a_{n-3} \qquad n\geq 3 \end{align*}

We see that $a_n=a_{n-3}$ for all $n\geq 3$.

So, calculating the first three values $a_0,a_1,a_2$ give all $a_n, n\geq 0$.

We find \begin{align*} a_0&=\sum_{k=0}^0\binom{0-k}{k}(-1)^k=\binom{0-0}{0}(-1)^0=1\\ a_1&=\sum_{k=0}^1\binom{1-k}{k}(-1)^k=\binom{1-0}{0}(-1)^0=1\\ a_2&=\sum_{k=0}^2\binom{2-k}{k}(-1)^k=\binom{2-0}{0}(-1)^0+\binom{2-1}{1}(-1)^1=1-1=0 \end{align*}

We conclude: $a_{6n}=a_{6n+1}=1,a_{6n+2}=a_{6n+5}=0,a_{6n+3}=a_{6n+4}=-1, n\geq 0$ and we get

\begin{align*} \sum_{k=0}^n\binom{n-k}{k}(-1)^k= \begin{cases} 1&n\equiv 0,1(6)\\ 0 &n\equiv 2,5(6)\\ -1 &n\equiv 3,4(6)\\ \end{cases} \end{align*}

Answer 2

$1.$ What is a closed form expression?

For instance, the closed form expression of $~\displaystyle\sum_{k=0}^{n-1}x^k~$ is $~\dfrac{1-x^n}{1-x~~}$ .

---

$2.$ How can I find a closed form expression for $A_n$ ?

The best way is by cheating ! :-$)$ Try and compute the values of the first few $A_n$ . You will notice that they form a repeating sequence of length $6$, starting with $n=0$. Try to prove this observation using induction, for instance.

---

As an aside, if the $(-1)^k$ were missing from the expression, $A_n$ would form the Fibonacci sequence. :-$)$

Answer 3

Suppose we seek to evaluate $$A_n = \sum_{k=0}^n {n-k\choose k}(-1)^k.$$

Introduce $${n-k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-k}}{z^{k+1}} \; dz.$$

Observe that this integral produces three segments of values according to $k$. Non-zero values while $n-k\ge k$ or $k\le \lfloor n/2\rfloor$, zero values when $\lfloor n/2\rfloor \lt k$ and $k\le n$ and non-zero values when $k>n,$ the latter because the power of $1+z$ migrates into the denominator, where the Newton binomial applies.

Therefore we may use the integral where $k$ ranges from zero to $n$ to obtain for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \sum_{k=0}^n \frac{(-1)^k}{(1+z)^k z^k}\; dz.$$

The sum is finite and the integral simplifies to $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \frac{1-(-1)^{n+1}/z^{n+1}/(1+z)^{n+1}}{1+1/z/(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n} \frac{1-(-1)^{n+1}/z^{n+1}/(1+z)^{n+1}}{z+1/(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n+1} \frac{1-(-1)^{n+1}/z^{n+1}/(1+z)^{n+1}}{z(1+z)+1} \; dz.$$

The first piece here is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n+1} \frac{1}{1+z+z^2} \; dz$$ for a contribution of zero.

The second piece is $$-\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n+1} \frac{(-1)^{n+1}/z^{n+1}/(1+z)^{n+1}}{z(1+z)+1} \; dz \\ = -\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{(-1)^{n+1}}{1+z+z^2} \; dz.$$

This is $$[z^{n}] \frac{(-1)^{n}}{1+z+z^2}.$$

The denominator corresponds to the recurrence $a_{n+2} = -a_{n+1}-a_n$ and from $n=0$ on the starting values are $1$ and $-1$ which yields $$1, -1, 0, 1, -1, 0, \ldots$$ with period three.

On the other hand $(-1)^{n}$ has period two, giving $$1, -1, 1, -1, 1, -1, \ldots$$

so that the product is the sequence with period six, $$1, 1, 0, -1, -1, 0,\ldots$$

Addendum. We could have observed that $$[z^{n}] \frac{(-1)^{n}}{1+z+z^2} = [z^{n}] \frac{1}{1-z+z^2}$$ for a recurrence of $b_{n+2} = b_{n+1}-b_n$ with initial values $1$ and $1$ producing once more $$1,1, 0, -1,-1, 0, 1, 1,\ldots$$