Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove this will be appreciated but a combinatorial solution is greatly preferred. Thanks for your help.

share|improve this question

5 Answers 5

up vote 5 down vote accepted
+50

Rewrite the identity with the index of summation changed from $i$ to $j$ where $j=i-k+1$: $$\sum_{j=1}^{n+1-k}(-1)^{j-1}\binom{n+1}{k+j}\binom{k+j-1}k=1.$$ Define a "good word" to be a word of length $n+1$ over the alphabet $\{A,B,C\}$ satisfying the conditions: there are exactly $k$ $C$'s, there is at least one $B$, and the first $B$ precedes all the $C$'s.

If $j$ is the number of $B$'s in a good word, then we must have $1\le j\le n+1-k$; moreover, the number of good words with exactly $j$ $B$'s is given by the expression $$\binom{n+1}{k+j}\binom{k+j-1}k.$$ The combinatorial meaning of the identity is that the number of good words with an odd number of $B$'s is one more than the number of good words with an even number of $B$'s. Here is a bijective proof of that fact.

Let $w$ be the word consisting of a single $B$ preceded by $n-k$ $A$'s and followed by $k$ $C$'s; this is a good word with an odd number of $B$'s. Let $W$ be the set of all good words different from $w$; we have to show that $W$ contains just as many words with an odd as with an even number of $B$'s. To see this, observe that the operation of switching the last non-$C$ letter in a word (from $A$ to $B$ or from $B$ to $A$) is an involution on $W$ which changes the parity of the number of $B$'s.

share|improve this answer
    
Thanks for your answer, it was exactly the type of thing I was looking for! –  Craig Oct 7 '13 at 13:42

This is a combinatorial proof of $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ It can be rearranged to $$\sum_{i=k+2t } \binom{i}{k} \binom{n+1}{i+1} = 1+ \sum_{i=k+1+2t} \binom{i}{k} \binom{n+1}{i+1} $$

I prefer to talk about choosing $i$ elements from a set whith $n$ elements to choosing $i+1$ elements from a set with $n+1$ elements so I substitute $i$ by $i-1$, $k$ by $k-1$ and $n$ by $n-1$ and get $$\sum_{i=k+2t } \binom{i-1}{k-1} \binom{n}{i} = 1+ \sum_{i=k+1+2t} \binom{i-1}{k-1} \binom{n}{i} \tag{1} $$

One well known interpretation of $\binom{n}{i}$ is as the number of subsets with $i$ elements of the set $ \{1,2,\ldots,n \}$.

if $n=9$ then $\{2,3,4,6,8\}$ is a subset with $i=5$ elements of $\{1,2,3,4,5,6,7,8,9\}$. Note that in the notation of the subsequence we find $i-1=4$ commas (","). Let's select two of this commas an replace them by "} {". We get $\big\{\{2\}\;\{3,4\}\;\{6,8\}\big\}$ if we replace the first and the third comma. So $\binom{i-1}{k-1}$ can be interpreted as the number of the ways a set with $i$ elements can be splitted into $k$ nonempty subsets $ A_r$ such that for each pair A, B of such subsets the following holds: $$(a \lt b, \;\; \forall a \in A, \forall b \in B) \;\;\text{or} \;\; (a \gt b, \;\; \forall a \in A, \forall b \in B)$$

The product $\binom{i-1}{k-1} \binom{n}{i}$ can be interpreted as the number of ways we can find $k$ subsets $A_j$ of $\{1,2,\ldots,n \}$ such that $$ A_r \cap A_s = \emptyset, \forall 1 \le r \lt s \le k \tag{2a}$$ $$ a_r \lt a_s, \forall a_r \in A_r, \forall a_s \in A_s, 1 \le r \lt s \le k \tag{2b}$$ $$ \sum_{r=1}^{k}|A_r|=i \tag{2c}$$

We call the set of all $\{A_1,\ldots \}$ that satisfy $(2)$ as $\Omega_{n,k,i}$. We have already seen that $$|\Omega_{n,k,i}|=\binom{i-1}{k-1} \binom{n}{i} \tag{3}$$ Because of $(2c)$ $$\Omega_{n,k,i} \cap \Omega_{n,k,j} = \emptyset, \; \; \forall i \ne j \tag{4}$$

We define $$\Omega_{n,k}'' = \cup_{i=k+2t , i \le n,t \in \mathbb{N_0}} \Omega_{n,k,i}$$ and $$\Omega_{n,k}' = \cup_{i=k+1+2t , i \le n,t \in \mathbb{N_0}} \Omega_{n,k,i}$$ and $$\Omega_{n,k} = \cup_{i=k}^{n} \Omega_{n,k,i}= \Omega_{n,k}'' \cup \Omega_{n,k}'$$

It follows from $(4)$ and $(3)$ that $$|\Omega_{n,k}''| = \sum_{i=k+2t , i \le n,t \in \mathbb{N_0}} \binom{i-1}{k-1} \binom{n}{i}$$ an $$|\Omega_{n,k}'| = \sum_{i=k+1+2t , i \le n,t \in \mathbb{N_0}} \binom{i-1}{k-1} \binom{n}{i}$$

So to prove $(1)$ we have to show that there is a bijection $\phi$ from $\Omega_{n,k}'' \backslash \{\text{one element}\}$ to $\Omega_{n,k}'$. Let $\omega=\{A_1,\ldots, A_k\}$ an element from $\Omega_{n,k}$.

  • If $n \notin A_k$ we define $\phi(\{A_1,\ldots, A_{k-1}, A_k\})=\{A_1,\ldots, A_{k-1}, A_k \cup \{n\} \}$
  • If $n \in A_k$ and $ A_k \ne \{n\}$ we define $\phi(\{A_1,\ldots, A_{k-1}, A_k\})=\{A_1,\ldots, A_{k-1}, A_k \backslash \{n\} \}$

$\phi$ defined so far is a bijection from $\Omega_{n,k}'' \backslash \Theta_k $ to $\Omega_{n,k}' \backslash \Theta_k $. $\Theta_k $ is $\{A_1,\ldots, A_{k-1}, \{n\} \}$

But if $\omega \in \Theta_n$ there is a problem. $A_k \backslash \{n\}= \emptyset$ and $\{A_1,\ldots, A_{k-1}, \emptyset \} $ is not in $\Omega_{n,k}$. How can we extend $\phi$ to $\Theta_k$?

Recursively!

  • If $n-1 \notin A_{k-1}$ we define $\phi(\{A_1,\ldots, A_{k-2}, A_{k-1}, \{n\} \})=\{A_1,\ldots, A_{k-2}, A_{k-1}\cup \{n-1\}, \{n\} \}$
  • If $n-1 \in A_{k-1}$ and $ A_{k-1} \ne \{n-1\}$ we define $\phi(\{A_1,\ldots, A_{k-2}, A_{k-1}, \{n\} \})=\{A_1,\ldots, A_{k-2} , A_{k-1} \backslash \{n-1\} , \{n\} \}$

Now we have extended $\phi$ to $\Theta_n \backslash \Theta_{n-1}$. This process can be continued. Finally we arrive at the following definition for $\phi$:

For $\{A_1,\ldots, A_r\}, \;A_j \ne \{n-j\}, \; A_{r-t}=\{n-t\}, t=0,\ldots,j-1$ we define

  • $\phi(\{A_1,\ldots, A_r\})=\{A_1,\ldots, A_{j-1},A_j \cup \{n-j\},\{n-j+1\},\ldots,\{n\}\}$ if $\{n-j\} \notin A_j $
  • $\phi(\{A_1,\ldots, A_r\})=\{A_1,\ldots, A_{j-1},A_j \backslash \{n-j\},\{n-j+1\},\ldots,\{n\}\}$ if $\{n-j\} \in A_j $

$\phi$ is not defined for $\{\{n-k+1\},\ldots,\{n\}\}$ but it is a bijection from $\Omega_{n,k}'' \backslash \{\{n-k+1\},\ldots,\{n\}\}$ to $\Omega_{n,k}'$. Therefore $(1)$ holds.

an example

For $n=5$, $k=3$ we get the following mapping $\phi$

$$ \begin{array}{l|l} \hline{} \\ \omega & \phi(\omega) \\ \hline{} \\ \Omega_{5,3,3} \subset \Omega_{5,3}'' & \subset \Omega_{5,3}' \\ \hline{} \\ \{1\}\;\{2\}\;\{3\} & \{1\}\;\{2\}\;\{3,5\}\\ \{1\}\;\{2\}\;\{4\} & \{1\}\;\{2\}\;\{4,5\}\\ \{1\}\;\{2\}\;\{5\} & \{1\}\;\{2,4\}\;\{5\}\\ \{1\}\;\{3\}\;\{4\} & \{1\}\;\{3\}\;\{4,5\}\\ \{1\}\;\{3\}\;\{5\} & \{1\}\;\{3,4\}\;\{5\}\\ \{1\}\;\{4\}\;\{5\} & \{1,3\}\;\{4\}\;\{5\}\\ \{2\}\;\{3\}\;\{4\} & \{2\}\;\{3\}\;\{4,5\}\\ \{2\}\;\{3\}\;\{5\} & \{2\}\;\{3,4\}\;\{5\}\\ \{2\}\;\{4\}\;\{5\} & \{2,3\}\;\{4\}\;\{5\}\\ \{3\}\;\{4\}\;\{5\} & \text{no image} \\ \hline{} \\ \Omega_{5,3,4} \subset \Omega_{5,3}' & \subset \Omega_{5,3}'' \\ \hline{} \\ \{1\}\;\{2\}\;\{3,4\} & \{1\}\;\{2\}\;\{3,4,5\} \\ \{1\}\;\{2,3\}\;\{4\} & \{1\}\;\{2,3\}\;\{4,5\} \\ \{1,2\}\;\{3\}\;\{4\} & \{1,2\}\;\{3\}\;\{4,5\} \\ \{1\}\;\{2\}\;\{3,5\} & \{1\}\;\{2\}\;\{3\} \\ \{1\}\;\{2,3\}\;\{5\} & \{1\}\;\{2,3,4\}\;\{5\} \\ \{1,2\}\;\{3\}\;\{5\} & \{1,2\}\;\{3,4\}\;\{5\} \\ \{1\}\;\{2\}\;\{4,5\} & \{1\}\;\{2\}\;\{4\} \\ \{1\}\;\{2,4\}\;\{5\} & \{1\}\;\{2\}\;\{5\} \\ \{1,2\}\;\{4\}\;\{5\} & \{1,2,3\}\;\{4\}\;\{5\} \\ \{1\}\;\{3\}\;\{4,5\} & \{1\}\;\{3\}\;\{4\} \\ \{1\}\;\{3,4\}\;\{5\} & \{1\}\;\{3\}\;\{5\} \\ \{1,3\}\;\{4\}\;\{5\} & \{1\}\;\{4\}\;\{5\} \\ \{2\}\;\{3\}\;\{4,5\} & \{2\}\;\{3\}\;\{4\} \\ \{2\}\;\{3,4\}\;\{5\} & \{2\}\;\{3\}\;\{5\} \\ \{2,3\}\;\{4\}\;\{5\} & \{2\}\;\{4\}\;\{5\} \\ \hline{} \\ \Omega_{5,3,5} \subset \Omega_{5,3}'' & \subset \Omega_{5,3}' \\ \hline{} \\ \{1,2,3\}\;\{4\}\;\{5\} & \{1,2\}\;\{4\}\;\{5\} \\ \{1,2\}\;\{3,4\}\;\{5\} & \{1,2\}\;\{3\}\;\{5\} \\ \{1,2\}\;\{3\}\;\{4,5\} & \{1,2\}\;\{3\}\;\{4\} \\ \{1\}\;\{2,3,4\}\;\{5\} & \{1\}\;\{2,3\}\;\{5\} \\ \{1\}\;\{2,3\}\;\{4,5\} & \{1\}\;\{2,3\}\;\{4\} \\ \{1\}\;\{2\}\;\{3,4,5\} & \{1\}\;\{2\}\;\{3,4\} \\ \hline{} \end{array} $$

share|improve this answer
    
Nice proof. A small typo: If I understood it correctly, the first row in your table should be mapped to $\{1\}\{2\}\{3,5\}$ instead of $\{1\}\{2\}\{3,4\}$. –  EuYu Oct 3 '13 at 12:52
    
Your are right, thank you, i will change this. –  miracle173 Oct 3 '13 at 16:57

I haven't yet come up with a combinatorial proof, but a proof using induction and the binomial formula is straightforward enough.

We fix $k \geqslant 0$ and use induction on $n \geqslant k$. The base case $n = k$ is simply

$$\sum_{i=k}^k (-1)^{i-k}\binom{i}{k}\binom{k+1}{i+1} = (-1)^0 \binom{k}{k}\binom{k+1}{k+1} = 1.$$

For the induction step, we have

$$\begin{align} \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\binom{n+2}{i+1} &= \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\left\lbrace \binom{n+1}{i+1} + \binom{n+1}{i}\right\rbrace\\ &=\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1} + \sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}\\ &=\underbrace{\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1}}_1 + \underbrace{\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}}_{m(k,n)} \end{align}$$

where in the first sum on the right the term for $i = n+1$ vanishes since $\binom{n+1}{n+1+1} = 0$ and the remainder is the sum for $n$, which is $1$ by the induction hypothesis.

It remains to see that $m(k,n) = 0$. But that is the coefficient of $x^k$ in

$$\begin{align} x^{n+1} &= \bigl(1 - (1-x)\bigr)^{n+1}\\ &= \sum_{i=0}^{n+1} (-1)^i\binom{n+1}{i}(1-x)^i\\ &= \sum_{i=0}^{n+1} \sum_{k=0}^i (-1)^{i+k}\binom{i}{k}\binom{n+1}{i}x^k\\ &= \sum_{k=0}^{n+1}\left(\sum_{i=k}^{n+1}(-1)^{i+k}\binom{i}{k}\binom{n+1}{i}\right)x^k, \end{align}$$

since $(-1)^{i+k} = (-1)^{i-k}$. We have $k \leqslant n < n+1$, hence the coefficient is $0$.

share|improve this answer

Here is another algebraic proof. Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

The sum we are trying to evaluate is $$\sum_{k=j}^n (-1)^{k-j} {k\choose j} {n+1\choose k+1} = (n+1) \sum_{k=j}^n \frac{(-1)^{k-j}}{k+1} {k\choose j} {n\choose k}.$$ Now let $$A_1(z) = \sum_{k\ge 0} (-1)^{k-j} {k\choose j} \frac{z^k}{k!} = \frac{1}{j!} \sum_{k\ge j} (-1)^{k-j} \frac{z^k}{(k-j)!} \\= \frac{1}{j!} z^j \sum_{k\ge j} (-1)^{k-j} \frac{z^{k-j}}{(k-j)!} = \frac{1}{j!} z^j \exp(-z).$$ It then follows that $$ A(z) = \sum_{k\ge 0} \frac{(-1)^k}{k+1} {k\choose j} \frac{z^k}{k!} = \frac{1}{z} \left(C + \int A_1(z) dz\right)$$ with $C$ a constant to be determined.

Now it is not difficult to show (consult the end of this post) that $$\int A_1(z) dz = -\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}$$ and we must have $$C = -[z^0] \left(-\exp(-z) \sum_{q=0}^j \frac{z^q}{q!} \right)= 1$$ so that $$A(z) = \frac{1}{z} \left(1 -\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}\right).$$ We have now determined $A(z)$ for the convolution of the two generating functions.

We take $$B(z) = \sum_{k\ge 0} \frac{z^k}{k!} = \exp(z).$$ It follows that $$A(z) B(z) = \frac{1}{z} \left(\exp(z) - \sum_{q=0}^j \frac{z^q}{q!}\right).$$ Now applying the coefficient extraction operator we get for $n\ge j$ that $$(n+1) n! [z^n] A(z) B(z) = (n+1)! [z^{n+1}] \left(\exp(z) - \sum_{q=0}^j \frac{z^q}{q!}\right).$$ None of the terms from the sum contribute because $n+1>j$ so that we are left with $$(n+1)! [z^{n+1}] \exp(z) = (n+1)! \frac{1}{(n+1)!} = 1.$$

Verification. $$\left(-\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}\right)' = \exp(-z) \sum_{q=0}^j \frac{z^q}{q!} - \exp(-z) \sum_{q=0}^{j-1} \frac{z^q}{q!} = \exp(-z) \frac{z^j}{j!}.$$

share|improve this answer

Wolfram Alpha yields this result:

enter image description here

It's here !!!

It's too bad for Wolfram Alpha that ${\bf they\ don't\ say}$ that the right hand side is identical to $\color{#0000ff}{\large\mbox{ONE}\ = 1}$.

share|improve this answer
    
The assumptions that $k,n$ are positive integers goes a long way to simplify this. It's indeed just 1. –  Alex R. Oct 5 '13 at 5:02
    
@AlexR. It's true. But if I got a result likes $1.35$, I don't write, for example $\displaystyle{\large{2.7 \over 2}\,{\sqrt{2\,}\,\sqrt{3\,} \over \sqrt{6\,}}}$. I write a plain $\large 1.35$. –  Felix Marin Oct 7 '13 at 6:08
    
It does, if you use the FunctionExpand[...] command. –  Lucian Oct 14 '13 at 17:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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