3

$$(x+m+1)\sum_{j=0}^{m}(-1)^jC_j{x+j\choose m-j}=F(x,m)\tag1$$

$C_n:=(1,1,2,5,14,42,132,...)$ this is the Catalan numbers

Claiming that $$F(x,m)=2(x-m){x\choose m}-(x-m-1){x-1\choose m}\tag2$$

Is the closed form to $(1)$ correct?

Can $(2)$ be simplify more further?

  • (2) can be rewritten as $F(x,m)=(x-m)\left( 1+\frac{m+1}{x} \right) \binom{x}{m}=(x-m)\left( \frac{x+m+1}{x} \right) \binom{x}{m}$ which is a slight simplification. Therefore you can divide through by $(x+m+1)$ before proving. – James Arathoon Dec 18 '17 at 14:24
  • Actually if you do divide through by $(x+m+1)$ you can simplify the conjecture further to $\binom{x-1}{m}=\sum_{j=0}^{m}(-1)^jC_j{x+j\choose m-j}$ – James Arathoon Dec 19 '17 at 01:38
  • In the book "Proofs that Really Count: The Art of Combinatorial Proof" by Arthur Benjamin and Jennifer Quinn (2003). On page 82 they prove another alternating sign identity involving $\binom{n-1}{m}$; slightly rearranged it is $\binom{n-1}{m}=(-1)^m \sum_{k=0}^m (-1)^k \binom{n}{k}$ – James Arathoon Dec 19 '17 at 03:07

2 Answers2

1

We can use formal power series to show that

$$\sum_{j=0}^m (-1)^j C_j {q+j\choose m-j} = {q-1\choose m}.$$

Start from

$$\sum_{j=0}^m (-1)^j C_j {q+j\choose m-j} = \sum_{j=0}^m (-1)^j C_j [z^{m-j}] (1+z)^{q+j} \\ = [z^m] (1+z)^q \sum_{j=0}^m (-1)^j C_j z^j (1+z)^j.$$

Now when $j\gt m$ we get zero from the coefficient extractor and hence we may extend the sum to infinity, obtaining from the generating function of the Catalan numbers that

$$[z^m] (1+z)^q \sum_{j\ge 0} (-1)^j C_j z^j (1+z)^j \\ = [z^m] (1+z)^q \frac{1-\sqrt{1-4\times -1 \times z(1+z)}} {2\times -1 \times z (1+z)} \\ = -\frac{1}{2} [z^m] (1+z)^q \frac{1-\sqrt{1+4z(1+z)}}{z(1+z)} \\ = -\frac{1}{2} [z^{m+1}] (1+z)^{q-1} (1-\sqrt{(1+2z)^2}) \\ = -\frac{1}{2} [z^{m+1}] (1+z)^{q-1} (-2z) = [z^m] (1+z)^{q-1} = {q-1\choose m}$$

as claimed.

Remark. With formal power series we really have

$$\sqrt{(1+pz)^2} = 1+pz$$

since we get on the LHS

$$\sum_{k\ge 0} {1/2\choose k} p^kz^k (2+pz)^k = 1 + \frac{1}{2} pz (2+pz) + \sum_{k\ge 2} {1/2\choose k} p^kz^k (2+pz)^k.$$

We have for $k\ge 2$ that

$${1/2\choose k} = \frac{1}{k!} \prod_{m=0}^{k-1} (1/2-m) = \frac{1}{2} \frac{1}{k!} \prod_{m=0}^{k-2} (-1/2-m) = \frac{1}{2} \frac{(-1)^{k-1}}{2^{k-1} k!} \prod_{m=0}^{k-2} (2m+1) \\ = \frac{1}{2} \frac{(-1)^{k-1}}{2^{k-1} k!} \frac{(2k-3)!}{(k-2)! 2^{k-2}} = \frac{1}{2^{2k-2}} (-1)^{k-1} \frac{1}{k} {2k-3\choose k-2}.$$

Extracting the coefficient we obtain for $q\ge 2$

$$[z^q] \sum_{k\ge 2} {1/2\choose k} p^kz^k (2+pz)^k = \sum_{k=2}^q {1/2\choose k} p^k [z^{q-k}] (2+pz)^k \\ = \sum_{k=2}^q {1/2\choose k} p^k {k\choose q-k} p^{q-k} 2^{2k-q} = \frac{1}{2^q} p^q \sum_{k=2}^q {1/2\choose k} {k\choose q-k} 2^{2k} \\ = \frac{1}{2^q} p^q \sum_{k=2}^q {k\choose q-k} 2^{2k} \frac{1}{2^{2k-2}} (-1)^{k-1} \frac{1}{k} {2k-3\choose k-2} \\ = \frac{1}{2^{q-2}} p^q \sum_{k=2}^q {k\choose q-k} (-1)^{k-1} \frac{1}{k} {2k-3\choose k-2}.$$

We get for $q=2$ the term $p^2 \times -1/2$ which yields for our series

$$1+\frac{1}{2} pz (2 + pz) - \frac{1}{2} p^2 z^2 = 1 + pz$$

which is correct so far. Continuing with $q\ge 3$ we see that the binomials are

$$\frac{(2k-3)!}{(q-k)! (2k-q)! \times (k-2)!} = \frac{1}{q-2} {2k-3\choose q-3} {q-2\choose k-2}$$

giving for our sum

$$\frac{1}{2^{q-2}} \frac{p^q}{q-2} \sum_{k=2}^q {2k-3\choose q-3} {q-2\choose k-2} (-1)^{k-1} \\ = \frac{1}{2^{q-2}} \frac{p^q}{q-2} \sum_{k=0}^{q-2} {2k+1\choose q-3} {q-2\choose k} (-1)^{k+1} \\ = \frac{1}{2^{q-2}} \frac{p^q}{q-2} \sum_{k=0}^{q-2} {q-2\choose k} (-1)^{k+1} [z^{q-3}] (1+z)^{2k+1} \\ = \frac{1}{2^{q-2}} \frac{p^q}{q-2} [z^{q-3}] (1+z) \sum_{k=0}^{q-2} {q-2\choose k} (-1)^{k+1} (1+z)^{2k} \\ = - \frac{1}{2^{q-2}} \frac{p^q}{q-2} [z^{q-3}] (1+z) (1-(1+z)^2)^{q-2} \\ = (-1)^{q-1} \frac{1}{2^{q-2}} \frac{p^q}{q-2} [z^{q-3}] (1+z) z^{q-2} (2+z)^{q-2} = 0.$$

No other terms appear in the series which is what we wanted to show.

Marko Riedel
  • 61,317
0

Pardon me if this solution seems clumsy to you, but I am trying to solve this with minimal invocation of generating functions an more combinatorics intuition.

For your simplification problem, I believe that what James Arathoon provided, or something equivalent, is the best you can do. But I actually need a polynomial in $x$, so I still will stick in equation (2).

Let $G(x) = 2(x-m)\binom xm - (x-m-1)\binom{x-1}m$ be the right hand side of (2). For a fixed $m$, note that both $F(x)$ and $G(x)$ are polynomials of degree $m+1$, it is sufficient to prove that $F(a) = G(a)$ for $a = 0, 1, \cdots, m+1$. To be more concrete, Lemma 1 below implies your equation (2):

Lemma 1: For a fixed $m$,

$$ \binom{m}{0}C_m - \binom{m-1}1 C_{m-1} + \cdots + (-1)^{\lfloor\frac m2\rfloor}\binom{m-\lfloor \frac m2\rfloor}{\lfloor\frac m2\rfloor}C_{m-\lfloor \frac m2 \rfloor} = 1, $$

$$ \binom{m+1}{0}C_m - \binom{m}1 C_{m-1} + \cdots + (-1)^{\lfloor\frac{m+1}{2}\rfloor}\binom{(m+1)-\lfloor \frac {m+1}2\rfloor}{\lfloor\frac {m+1}2\rfloor}C_{m-\lfloor \frac {m+1}2 \rfloor} = 0, $$

$$ \vdots $$

$$ \binom{2m}{0}C_m - \binom{2m-1}1 C_{m-1} + \cdots + (-1)^m\binom{m}{m}C_{0} = 0, $$

$$ \binom{2m+1}{0}C_m - \binom{2m}1 C_{m-1} + \cdots + (-1)^m\binom{m+1}{m}C_{0} = (-1)^{m}. $$

We will use induction on $m$ to prove Lemma 1. An important fact used to hinge equations among different $m$'s will be Lemma 2:

Lemma 2: For each $m$,

$$ \binom{2m}{0}C_m - \binom{2m-1}1 C_{m-1} + \cdots + (-1)^m\binom{m}{m}C_{0} = 0. $$

Proof of Lemma 1: Start with the base case $m=1$. This is valid because

$$ \binom 10 C_1 = 1, \binom 20 C_1 - \binom 11 C_0 = 0, \mbox{ and } \binom 30 C_1 - \binom 21 C_0 = -1. $$

Suppose the assertion holds when $m = k$ and Lemma 2 holds. When $m= k+1$. since

$$ \binom{2k+2}{0}C_{k+1} - \binom{2k+1}1 C_{k} + \cdots + (-1)^{k+1}\binom{k+1}{k+1}C_{0} = 0 $$ and $$ \binom{2k+1}{0}C_k - \binom{2k}1 C_{k-1} + \cdots + (-1)^k\binom{k+1}{k}C_{0} = (-1)^{k}, $$

subtract the second equation from the first, and using the binomial formula $\binom ab = \binom{a-1}b + \binom a{b-1}$, we get

$$ \binom{2k+2}{0}C_{k+1} - \binom{2k+1}1 C_{k} + \cdots + (-1)^{k+1}\binom{k+2}{k+1}C_{0} = (-1)^{k+1}, $$

which is the last equation in Lemma 1 when $m = k+1$. The other equations can be derived in the similar way.

This concludes the proof of Lemma 1.

Proof of Lemma 2: We provide a combinatoric proof for this lemma. From this, we describe $C_n$ as the number of sequences of length $2n$ consisting of $n$ $A$'s and $n$ $B$'s so that whenever we take the first $0< k < 2n$ letters, the number of $A$'s is no less than that of $B$'s.

(For instance, $C_3 = 5$ because we have the following five sequences $AAABBB$, $AABABB$, $AABBAB$, $ABAABB$, $ABABAB$. We call a length $2n$ sequence of this form an $2n$-admissible sequence).

Let $0 \leq j \leq n$. We now define a way to construct a $2n$-admissible sequence from $2(n-j)$-admissible sequences. We can first start the sequence with $j$ $A$'s. For the remaining $2n-j$ slots, pick $j$ slots and put them in $B$, and then fill a $2(n-j)$-admissible sequence. It can be shown that the resulting $2n$ sequence is admissible. And clearly there are $\binom{2n-j}{j}$ ways to generate $2n$-admissible sequences from a $2(n-j)$-admissible sequence.

For instance, from the $4$-admissible sequence $ABAB$, we can generate five $6$-admissible sequences: $AB\color{red}{ABAB}$, $A\color{red}{A}B\color{red}{BAB}$, $A\color{red}{AB}B\color{red}{AB}$, $A\color{red}{ABA}B\color{red}{B}$, and $A\color{red}{ABAB}B$.

Note that in total there are $\binom{2n-j}jC_{n-j}$ ways to extend $2(n-j)$-admissible sequences to $2n$-admissible sequences. Let us now look at any $2n$-admissible sequence, where we denote it by $S_n$, and see how many ways it can be extended from shorter sequences. For each $j$, let $S_{n,j}$ be the number of ways that $S_n$ can be extended from a $2(n-j)$-admissible sequence.

For example, if $S_4 = AAABBABB$, then $S_{4,0} = 1$, $S_{4, 1} = 4$, $S_{4, 2} = 5$ and $S_{4, 3} = 2$. So $S_{4, even} = 1+5 = 6$ and $S_{4, odd} = 4 + 2 = 6$.

The alternative sum in Lemma 2 then follows from the following Lemma 3.

This concludes the proof of Lemma 2.

Lemma 3: For any $2n$-admissible sequnce $S_n$, $S_{n, even} = S_{n, odd}$.

Proof of Lemma 3: Finally we are not able to avoid generating functions (ugh!). Let

$$ E_{S_n}(x) = \sum_{j=0}^n (-1)^jS_{n, j}x^j. $$

Then Lemma 3 holds if $(1-x)|E_{S_n}(x)$.

Actually we can do better: Let $c$ be the length of the first $B$ chunk in $S_n$. Then we have $(1-x)^c|E_{S_n}(x)$. (For example, consider again $S_4 = AAABBABB$. Then $c = 2$ and $E_{S_4}(x) = (1-x)^2(1-2x)$).

The reason that this is true can be observed by doing the reverse, that is, "removing pieces (some selected $B$'s and the starting $A$'s) from $S_n$". It turns out that if you removed some $B$'s not in the first chunk, you can always remove any number of $B$'s from the first chunk and the resulting shorter sequence is still admissible. This will provide the $(1-x)^c$ factor, because removal from the first chunk is independent to the removal of the rest.

This concludes the proof of Lemma 3.

Hw Chu
  • 5,761
  • This proof is very difficult to follow. Lemma 1 and Lemma 2 seem all mixed up together and confused. Are there some typos when referencing either Lemma 1 or Lemma 2? – James Arathoon Dec 19 '17 at 01:48
  • For a fixed $m$, Lemma 1 consists of $m+1$ equations and Lemma 2 is one of the $m+1$ equations in Lemma 1. Lemma 1 is proved by induction and Lemma 2, while Lemma 2 is proved by combinatorics or generating functions (in Marko Riedel's answer). I don't think there was a typo in referring. – Hw Chu Dec 19 '17 at 02:47