# Show that the sum of reciprocal products equals $n$ [closed]

(Original at https://i.stack.imgur.com/DRIX8.jpg)

Consider all non-empty subsets of the set $\{1, 2, \ldots, n\}$. For every such subset, we find the product of the reciprocals of each of its elements. Denote the sum of all these products as $S_n$. For example,

$$S_3 = \frac11 + \frac12 + \frac13 + \frac{1}{1\cdot2} + \frac{1}{1\cdot3} + \frac{1}{2\cdot3} + \frac{1}{1\cdot2\cdot3}$$

(a) Show that $S_n = \frac1n + \left(1 + \frac1n\right)S_{n-1}$.

(b) Hence or otherwise, deduce that $S_n = n$.

• God, how awful is "$2.3$"! "$1.2.3$" is a lemma, not a number.
– user228113
May 10, 2018 at 21:47
• Part A tells you exactly how to proceed! Jun 14, 2022 at 1:15

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.

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.

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.

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

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.

If we also include $$\frac{1}{\prod_{i\in\emptyset}i}=1$$, the sum factorizes viz.$$\sum_{S\subseteq\{1,\,\cdots,\,n\}}\prod_{i\in S}\frac{1}{i}=\prod_{i\in S}\left(1+\frac1i\right)=\prod_{i\in\{1,\,\cdots,\,n\}}\frac{i+1}{i}.$$This is a telescoping product, which you can prove is $$n+1$$ by induction. So the original sum is $$n+1-1=n$$.

Use Vieta's.

Consider monic polynomial $$f(x)$$ with roots $$-1/1, -1/2, -1/3, ... , -1/n.$$

Write $$f(x)$$ in standard form using Vieta's and also write $$f(x)$$ as a factored form.

So, in factored form, $$f(x)=(x+1/1)(x+1/2)(x+1/3)...(x+1/n).$$ Look back into the standard form, $$f(1)-1$$ is ur sum! (we subtract $$1$$ is because the leading coefficient of $$x^n$$ is not in the sum.)

and look at ur factored form, we can telescope !!