1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ @MaxDoc: You're welcome! :-) $\endgroup$ – Markus Scheuer Apr 30 '15 at 9:30
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.