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

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

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

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.

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.

Here is a probabilistic proof of the first equality.

Given $n$ urns, and each round, you place a ball into one of the $n$ urns randomly and uniformly. What is the expected number of rounds until every urn has a ball?

There are two approaches to solving this.

One approach uses inclusion-exclusion, which gives $$\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\frac{n}{k}.$$

The other approach let $X_k$ be the number of rounds to get balls in $k$ urns after you've gotten a ball in each of $k-1$ urns. Then it is easy to see that $E(X_k)=\frac{n}{n-k+1}$ and the expected time is $\sum_{k=1}^{n}\frac{n}{n-k+1}$ That can be rewritten as $$\sum_{k=1}^{n}\frac{n}{k}.$$

See this answer for details.