Closed Form Expression of sum with binomial coefficient 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:


*

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

*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.
 A: 
$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. :-$)$
A: 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*}

A: 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$$
