#### [SOLVED] Proving Binomial Identity without calculus

How to establish the following identities without the help of calculus:

For positive integer $n,$ $$\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r=\sum_{1\le r\le n}\frac1r$$

and $$\sum_{0\le r\le n}\frac{(-1)^r\binom nr}{4r+1}=\frac{4^n\cdot n!}{1\cdot5\cdot9\cdot(4n+1)}$$

#### @Sameer Kailasa 2018-04-15 01:34:08

Here is a purely combinatorial proof of the first identity:

Let us count the number $C$ of disjoint cycles in a given permutation $\sigma \in S_n$. On the one hand, we have simply $$C = \sum_{k=1}^{n} C_k$$ where $C_k$ is the number of $k$-cycles in $\sigma$. On the other hand, we can count by "inclusion-exclusion," as follows.

Denote the set $[n]:= \{1,2, 3, \cdots, n\}$. For each subset $S \subset [n]$, let $\chi(S) = 1$ if $S$ is contained wholly in some cycle of $\sigma$ and $0$ otherwise. Then, I claim we have $$C = \sum_{\emptyset \neq S \subset [n]} (-1)^{|S|-1} \chi(S)$$ To prove this, note that the only subsets of $[n]$ contributing to the sum are those contained in some cycle. For each cycle in $\sigma$ of size $k$, the contribution to the sum is $$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} -\cdots + (-1)^{k-1} \binom{k}{k}= 1-(1-1)^k = 1$$ by the binomial theorem; hence, the sum ultimately evaluates to just the number of cycles of $\sigma$.

Thus, we have the identity $$\sum_{k=1}^{n} C_k = \sum_{\emptyset \neq S \subset [n]} (-1)^{|S|-1} \chi(S) = \sum_{k=1}^{n} (-1)^{k-1} \sum_{\substack{S \subset [n] \\ |S| = k}} \chi(S)$$ Now, we suppose $\sigma$ is chosen uniformly at random from $S_n$ and compute the expected number of cycles in $\sigma$. By linearity of expectation, we have $$\sum_{k=1}^{n} \mathbb{E}[C_k] = \sum_{k=1}^{n} (-1)^{k-1}\mathbb{E} \left[ \sum_{\substack{S \subset [n] \\ |S| = k}} \chi(S) \right]$$

Now, we have to compute these expectations. Let us first calculate $\mathbb{E}[C_k]$. We have $$C_k = \frac{1}{k} \sum_{j=1}^{n} \mathbb{1}_{\text{contained in a } k-\text{cycle}} (j) \implies \mathbb{E}[C_k] = \frac{n}{k} \text{Prob}(\text{fixed element contained in } k-\text{cycle})$$ and $$\mathbb{E} \left[ \sum_{\substack{S \subset [n] \\ |S| = k}} \chi(S) \right] = \binom{n}{k} \text{Prob}(\text{fixed set of size } k \text{ contained in some cycle})$$

The evaluation of these probabilities is classical (see Terry Tao's post or this Wikipedia article), and we have $$\text{Prob}(\text{fixed element contained in } k-\text{cycle}) = \frac{1}{n}$$ $$\text{Prob}(\text{fixed set of size } k \text{ contained in some cycle}) = \frac{1}{k}$$ hence the final conclusion follows.

#### @marty cohen 2018-04-15 02:49:49

To me, this proof is much harder than the calculus proof, as well as being much harder to discover. The calculus proof of Felix Marin is straightforward and natural, while this is magic.

#### @Felix Marin 2017-06-13 04:25:56


$\ds{\Huge\left.2\right):} \bbox[15px,#ffd]{\ds{% \sum_{0\ \leq\ r\ \leq\ n}{\pars{-1}^{r}{n \choose r} \over 4r + 1} = {4^{n}\,n! \over 1 \cdot 5 \cdot 9 \cdot \pars{4n + 1}}:\ {\large ?}}}$. \begin{align} \sum_{0\ \leq\ r\ \leq\ n}{\pars{-1}^{\,r}\,{n \choose r} \over 4r + 1} & = \sum_{r = 0}^{n}\pars{-1}^{\,r}{n \choose r}\int_{0}^{1}t^{4r}\,\dd t = \int_{0}^{1}\sum_{r = 0}^{n}{n \choose r}\pars{-t^{4}}^{r}\,\dd t = \int_{0}^{1}\pars{1 - t^{4}}^{n}\,\dd t \\[5mm] & \stackrel{\large t^{4}\ \mapsto\ t}{=}\,\,\, {1 \over 4}\int_{0}^{1}t^{-3/4}\,\pars{1 - t}^{n}\,\dd t = {1 \over 4}\,{\Gamma\pars{1/4}\Gamma\pars{n + 1} \over \Gamma\pars{n + 5/4}} \\[5mm] & = {1 \over 4}\,n!\,{1 \over \Gamma\pars{1/4 + \bracks{n + 1}}/\Gamma\pars{1/4}} = {1 \over 4}\,n!\,{1 \over \pars{1/4}^{\,\overline{n + 1}}} \\[5mm] & = {1 \over 4}\,n!\,{1 \over \prod_{r = 0}^{n}\pars{1/4 + r}} = {1 \over 4}\,n!\,{1 \over \prod_{r = 0}^{n}\bracks{\pars{4r + 1}/4}} \\[5mm] & = {1 \over 4}\,n!\,{1 \over \bracks{\prod_{r = 0}^{n}\pars{4r + 1}}/4^{n + 1}} = \bbx{\ds{{4^{n}\,n! \over 1 \cdot 5 \cdot 9 \cdot \pars{4n + 1}}}} \end{align}

#### @marty cohen 2018-04-15 02:51:35

Your answer to 2 generalizes readily to $\sum_{r=0}^n \dfrac{(-1)^r\binom{n}{r}}{ar+b} = \dfrac{n!a^{n}}{\prod_{r=0}^n(ar+b)}$.

#### @Felix Marin 2018-04-18 02:42:28

@martycohen I guess so. Thanks.

#### @lab bhattacharjee 2013-12-25 12:15:35

For the first Question let $\displaystyle S_n=\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r$

$\displaystyle\implies S_{m+1}-S_m=\sum_{1\le r\le m+1}(-1)^{r-1}\frac{\binom{m+1}r-\binom mr}r-\binom m{m+1}\frac{(-1)^m}{m+1}$

$\displaystyle=\sum_{1\le r\le m+1}(-1)^{r-1}\frac{\binom{m+1}r-\binom mr}r$ as $\binom mr=0$ for $r>m$ or $r<0$

Now using this formula, $\displaystyle\binom{m+1}r=\binom mr+\binom m{r-1}\iff \binom{m+1}r-\binom mr=\binom m{r-1}$

Again, $\displaystyle\frac{\binom m{r-1}}r=\frac{m!}{\{m-(r-1)\}!(r-1)!\cdot r}=\frac1{m+1}\cdot\frac{(m+1)!}{(m+1-r)!\cdot r!}$ $\displaystyle=\frac1{m+1}\cdot\binom{m+1}r$

$\displaystyle\implies S_{m+1}-S_m=\sum_{1\le r\le m+1}(-1)^{r-1}\cdot\frac1{m+1}\cdot\binom{m+1}r$ $\displaystyle=\frac1{m+1}\sum_{1\le r\le m+1}(-1)^{r-1}\binom{m+1}r$ $\displaystyle=\frac{1-(1-1)^{m+1}}{m+1}$

$\displaystyle\implies S_{m+1}-S_m=\frac1{m+1}$

Now, $\displaystyle S_1=\frac11$

As $\displaystyle S_2-S_1=\frac12\implies S_2=1+\frac12$ and so on

#### @OR. 2013-07-06 15:42:22

You can always use Petkovsek's algorithm. It only requires some algebra to prove this and other problems alike.

You can read about it in the book $A=B$ (available free online).

Another thing is that derivation of polynomials is a completely algebraic operation.

You can always write instead of $(P(x))'|_{x=1}$ write $[P(x+1)-P(1)]/x|_{x=0}$, perhaps what is equivalent, rewrite in powers of $(x-1)$, which involves iterated division by $(x-1)$. [I just pressed Alt+F7 to try to compile the LaTeX] And little by little hide the calculus from the proof that you have.