Proving that a recurrence holds for all n

[Mr Davis 97]

Homework Statement

Let $H=\{2,3,4, \dots , n\}$. Find a recurrence relation that involves the following number: $\displaystyle \sum_{G\subseteq H}\frac{1}{\prod_{x\in G}}$, where $G\not = \{\}$

Homework Equations

The Attempt at a Solution

If $H=\{2\}$, let $S_2$ be the sum. If $H=\{2,3\}$ let $S_3$ be the sum, and so on.

Now, I'm trying to find a recurrence relation, and from looking at small cases it's pretty obviously $S_n = S_{n-1} + \frac{1}{n}(1 + S_{n-1})$. But how exactly do I prove that this is a valid recurrence relation for all $n$?

 

[fresh_42]

I do not understand the question. I would take $G:=\{\,2\,\}$ and $S_n:=\sum_{G\subseteq H}\dfrac{1}{\prod_{x\in G}x} \equiv \dfrac{1}{2}$ does the job. Without the $x$ in the product, the entire sum is identical $1$. In either case $S_n=S_{n-1}$ is a valid recursion.

 

[Mr Davis 97]

I do not understand the question. I would take $G:=\{\,2\,\}$ and $S_n:=\sum_{G\subseteq H}\dfrac{1}{\prod_{x\in G}x} \equiv \dfrac{1}{2}$ does the job. Without the $x$ in the product, the entire sum is identical $1$. In either case $S_n=S_{n-1}$ is a valid recursion.

I don't think you can choose what $G$ is. The notation is to indicate that you are iterating over subsets of $H$

 

[fresh_42]

I don't think you can choose what $G$ is. The notation is to indicate that you are iterating over subsets of $H$

Even then. Without an expression in the product, the product is empty, and thus the entire expression in equal to $|G|$.

 

[Mr Davis 97]

Here is what I see.

If $H=\{2\}$ then $S_2 = \displaystyle \sum_{G\subseteq H}\frac{1}{\prod_{x\in G}x} = \frac{1}{2}$.

If $H = \{2,3\}$, then $S_3 = \displaystyle \sum_{G\subseteq H}\frac{1}{\prod_{x\in G}x} = \frac{1}{2} + \frac{1}{3} + \frac{1}{2\cdot 3} = 1$.

If $H = \{2,3,4\}$, then $S_4 = \displaystyle \sum_{G\subseteq H}\frac{1}{\prod_{x\in G}x} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{2\cdot 3} + \frac{1}{2\cdot 4} + \frac{1}{3\cdot 4} + \frac{1}{2\cdot 3 \cdot 4} = \frac{3}{2}$

Do you see? From here it's pretty clear that $S_n = S_{n-1} + \frac{1}{n}(1 + S_{n-1})$, but I don't know how to prove that this relation holds for all $n$, although it clearly does.

 

[Ray Vickson]

Even then. Without an expression in the product, the product is empty, and thus the entire expression in equal to $|G|$.

I suspect a typo: he probably means $\prod_{x \in G} x$, not $\prod_{x \in G}$ .

 

[fresh_42]

I suspect a typo: he probably means $\prod_{x \in G} x$, not $\prod_{x \in G}$ .

Yes, I misread the problem. Sum over all $G$ and product over all $x\in G$. I first thought it was a certain $G$ and sum and product over it's elements. But what's under the product (and missing) is quite essential. Maybe it's free to choose and one can find any recurrence depending on it.

 

[Mr Davis 97]

I suspect a typo: he probably means $\prod_{x \in G} x$, not $\prod_{x \in G}$ .

Sorry! Yes, I made a typo and what you wrote is correct.

 

[Mr Davis 97]

Yes, I misread the problem. Sum over all $G$ and product over all $x\in G$. I first thought it was a certain $G$ and sum and product over it's elements. But what's under the product (and missing) is quite essential. Maybe it's free to choose and one can find any recurrence depending on it.

So assuming that the recurrence relation is correct, how do I actually prove that it works for all $n$?

 

[fresh_42]

So assuming that the recurrence relation is correct, how do I actually prove that it works for all $n$?

Recursion and induction are a natural pairing. Observe which additional sets $G$ and with them summands have to be added in the step $n \to n+1$.

Edit: You will not need a formal induction unless you solve the recursion, but the process in the recursion is the same, from $n \to n+1$. In this case you get the formula straight away.

 

[Mr Davis 97]

Recursion and induction are a natural pairing. Observe which additional sets $G$ and with them summands have to be added in the step $n \to n+1$.

Edit: You will not need a formal induction unless you solve the recursion, but the process in the recursion is the same, from $n \to n+1$. In this case you get the formula straight away.

Is an argument such as this sufficient? Am I being rigorous enough?

We find a recurrence relation for $S_n$. Observe that $S_{n+1}$ equals $S_n$, but we must also take into account the additional element $n+1$, meaning that after accounting for $S_n$ we then sum over the reciprocal products again but with a $n+1$ always in the denominator. So then we can factor out the $\frac{1}{n+1}$ to get the quantity $\frac{1}{n+1}(1+S_{n})$. So we have that

$$S_{n+1} = S_n + \frac{1}{n+1}(1+S_{n}) = S_n(1 + \frac{1}{n+1}) + \frac{1}{n+1}.$$

 

[fresh_42]

Not quite sure. It looks a bit as if you only described what the formula says anyway. I would proceed more formally. First name $G=:G_n \subseteq H_n =\{\,1,\ldots ,n\,\}$. Dependencies should always be noted, otherwise they are a source for confusion and in more complicated situations, a possibility to cheat.

Now we have $\{G_{n+1}\} = \{G_n\} \cup \left( \{G_n \cup \{n+1\} \}\right) \cup \{n+1\}$. So $\sum_{G_{n+1}}=\sum_{G_n}+\sum_{G_n\cup \{n+1\}} + \sum_{\{n+1\}}$ where I omitted the products out of laziness. But it yields $$S_{n+1}= S_n + \sum_{G_n} \dfrac{1}{\left(\prod_{x\in G_n}x\right) \cdot (n+1)} + \dfrac{1}{n+1} = \ldots $$