Show that the sum of reciprocal products equals $n$

Solution 1:

You should add what you've tried. Anyway:

Use induction for the 1st argument. Obviously $S_1=1$ and $S_2=2=1/2+(1+1/2)S_1$, so the proposition is true for $n=2$. Assume that it is true for some $n$ and with that in hand prove it for $n+1$: We have $S_{n+1}=$ terms that $n+1$ does not appear on the denominator $+$ terms that $n+1%$ appears on the denominator $=S_n+\frac{1}{n+1}S_n+\frac{1}{n+1}$, since $\frac{1}{n+1}$ is a common factor of the elements that have $(n+1)$ as a divisor of the denumerator. By induction, this formula is true for all $n\in\mathbb{N}$. For the 2nd argument, use induction again. We already saw that $S_1=1$. Assume that $S_{n}=n$. Then use the formula proved above and get $S_{n+1}=n+\frac{n+1}{n+1}=n+1.$ These things are quite simple, try hard and don't give up easily.

Solution 2:

The case for n=1 is obvious.

Note that the power set of $\{1,2,3,..,k,k+1\}$ contains all subsets of $\{1,2,3,..,k\}$ along with subsets containing $k+1$

Thus $S_{k+1} = S_k + \frac {1}{k+1} + \frac {1}{k+1} (S_k)$

That is $S_{k+1} = \frac {1}{k+1} + (\frac {1}{k+1} +1) (S_k)$

Now we see that $S_k =k $ fits the above relation.

Solution 3:

Part (b):

The sum is given by, for example:

$$S_3=\left(1+\frac11\right)\left(1+\frac12\right)\left(1+\frac13\right)-1$$

In general:

$$S_n=\prod_{k=1}^n \left(1+\frac1k\right)-1$$

$$S_n=\prod_{k=1}^n \frac{k+1}{k}-1=n$$

by the rule of telescope.

Solution 4:

I'm a little late to the show, but I found a cute proof of this property that others have not covered.

First, we guess (as with all the other solutions) that $S_n = n$. Then multiply out by $n!$. We're left with $(n+1)! - n!$ on one side and a sum of things like

$$P(n_1, n_2, ..., n_k) = \frac{n!}{n_1n_2...n_k}, \quad 1 \le n_1<n_2 < ...< n_k \le n$$

on the other. Here's a counting interpretation of this quantity:

Imagine $n$ slots in a row, where the $i^{\text{th}}$ slot can hold a single number from between 1 and $i$ (inclusive). Then $P(n_1, n_2, ..., n_k)$ is the number of ways the $n$ slots can be filled (following the rules given) with the proviso that the slots numbered $n_1, n_2, ..., n_k$ remain empty.

Then clearly, the sum in question is simply the number of ways of filling the slots such that at least one remain empty. This is easy to calculate:

There are $i+1$ options for the $i^{\text{th}}$ slot (the numbers from 1 to $i$ and nothing at all), so that gives $(n+1)!$. But we need to remove the fillings with no empty slots, of which there are $n!$. And that's it.