Proving Binomial Identity without calculus

Question

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\cdots(4n+1)}$$

Answer 1

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.

Answer 2

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

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $\ds{\LARGE\left. {\bf 1}\right):} \bbox[15px,#ffd]{\ds{\sum_{1\ \leq\ r\ \leq\ n}{\pars{-1}^{\,r - 1}{n \choose r} \over r} = \sum_{1\ \leq\ r\ \leq\ n}{1 \over r}:\ {\large ?}}}$. \begin{align} \sum_{1\ \leq\ r\ \leq\ n}{\pars{-1}^{\,r-1}{n \choose r} \over r} & = \sum_{r = 1}^{n}\pars{-1}^{\,r - 1}{n \choose r}\int_{0}^{1}t^{r - 1}\,\dd t = -\int_{0}^{1}\sum_{r = 1}^{n}{n \choose r}\pars{-t}^{\,r}\,{\dd t \over t} \\[5mm] & = -\int_{0}^{1}{\pars{1 - t}^{n} - 1 \over t}\,\dd t = \int_{0}^{1}{t^{n} - 1 \over t - 1}\,\dd t = \int_{0}^{1}\sum_{r = 1}^{n}t^{r - 1}\,\dd t \\[5mm] & = \sum_{r = 1}^{n}\int_{0}^{1}t^{r - 1}\,\dd t = \bbx{\sum_{1\ \leq\ r\ \leq\ n}{1 \over r}} \\ & \end{align}

---

$\ds{\LARGE\left. {\bf 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 \cdots \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 \\[5mm] & = \int_{0}^{1}\pars{1 - t^{4}}^{n}\,\dd t \,\,\,\stackrel{\large t^{4}\ \mapsto\ t}{=}\,\,\, {1 \over 4}\int_{0}^{1}t^{-3/4}\,\pars{1 - t}^{n}\,\dd t \\[5mm] & = {1 \over 4}\,{\Gamma\pars{1/4}\Gamma\pars{n + 1} \over \Gamma\pars{n + 5/4}} = {1 \over 4}\,n!\,{1 \over \Gamma\pars{1/4 + \bracks{n + 1}}/\Gamma\pars{1/4}} \\[5mm] & = {1 \over 4}\,n!\,{1 \over \pars{1/4}^{\,\overline{n + 1}}} = {1 \over 4}\,n!\,{1 \over \prod_{r = 0}^{n}\pars{1/4 + r}} \\[5mm] & = {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 \cdots \pars{4n + 1}}}} \\ & \end{align}