Summing a series with binomial coefficients without calculus. The following problem is from a high school problem set. The students do not know how to integrate yet although they are comfortable with differentiation.
The problem is

Show that $\displaystyle S:=\sum_{k=0}^{n} (-1)^k \frac{\binom{n}{k}}{n+k}= \frac{1}{n \binom{2n}{n}}$.

This problem can be solved by beta functions. It turns out that
$$ S = \int_0^1 x^{n-1} (1-x)^n dx $$
when you expand the integrand using binomial theorem.
But are there any other, hopefully elementary, ways of solving the problem?
 A: A common technique is to strengthen the induction hypothesis.
In particular, integrating and expanding $x^{m-1}(1-x)^n$ gives a hint that we can consider using:
$$ \sum_{k=0}^n (-1)^k \frac{n \choose k}{m+k} = \frac{(m-1)!n!}{(m+n)!}$$
Let's do induction to show it's true for all $n$ starting at $0$.
If $n=0$, we have $\frac{1}{m}=\frac{(m-1)!0!}{m!}$.
Let $0 \leq n$. Let's show it being true for $n$ implies it's true for $n+1$.
We have starting with the LHS:
$$\sum_{k=0}^{n+1} (-1)^k \frac{n+1 \choose k}{m+k}=\sum_{k=0}^{n+1} (-1)^k \frac{{n \choose k}+{n\choose k-1}}{m+k}$$
$$=\sum_{k=0}^{n} (-1)^k \frac{{n \choose k}}{m+k}-\sum_{k=0}^{n} (-1)^k \frac{{n\choose k}}{m+1+k} $$
Using the inductive hypothesis for $n$:
$$=\frac{(m-1)!n!}{(m+n)!}-\frac{m!n!}{(m+n+1)!}$$
$$=\frac{(m-1)!n!}{(m+n)!} (1 -\frac{m}{m+n+1})$$
$$=\frac{(m-1)!n!}{(m+n)!} \frac{n+1}{m+n+1}$$
$$=\frac{(m-1)!(n+1)!}{(m+n+1)!}$$
Thus, if it's true for a given $n$, then it's true for $n+1$, finishing the inductive proof.
In particular, it's true when $m=n-1$ proving your initial equality.
