7
$\begingroup$

I was looking up riddles for my math classes to work on for the end of the year and found the following riddle. http://mathriddles.williams.edu/?p=129

I followed the advice and started working with examples of small numbers and stumbled upon a pattern that I wanted to generalize.

$$\frac{1}{2}(1)=0.5$$ $$\frac{1}{3}\left(1+\frac{1}{2}\right)=0.5$$ $$\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{2\cdot 3}\right)=0.5$$ $$\frac{1}{5}\left(1+\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}\right)=0.5$$ $$\frac{1}{6}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{2\cdot 3}+\frac{1}{2\cdot 4}+\frac{1}{2\cdot 5}+\frac{1}{3\cdot 4}+\frac{1}{3\cdot 5}+\frac{1}{4\cdot 5}+\frac{1}{2\cdot 3\cdot 4}+\frac{1}{2\cdot 3\cdot 5}+\frac{1}{2\cdot 4\cdot 5}+\frac{1}{3\cdot 4\cdot 5}+\frac{1}{2\cdot 3\cdot 4\cdot 5}\right)=0.5$$

If my pattern doesn't make sense, I'm taking $\frac{1}{n}$ and multiplying it by the sum of the reciprocals of all unique products for $2$ to $n-1$ and it comes out to 0.5 each time up to $n=7$ (I have not tested any higher values). Equivalently, if you multiply both sides by $n$ then subtract $1$, you see that all the reciprocals sum to $0.5n-1$.

I don't know where to start with generalizing this pattern as I have never seen explicit formulas for such sums, so I wanted to see if anyone knew if this was the case for all $n$ and how one could prove or disprove it.

$\endgroup$
  • 3
    $\begingroup$ For $n=7$, do you consider $\frac 16$ and $\frac 1{2\cdot3}$ different? $\endgroup$ – peterwhy Apr 29 '16 at 21:50
  • $\begingroup$ Yes. Each number is considered unique, prime or not. $\endgroup$ – Dirigible Apr 29 '16 at 23:10
1
$\begingroup$

Let $s_n$ be the sum of $1$ and the fractions for the $n$ case, e.g. $$s_4 = 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{2\cdot3}$$

Assume $s_k = k/2$ is true for some $k$.

For the $n=k+1$ case, $$s_{k+1} = s_k\cdot \left(1+\frac1k\right) = s_n\cdot\frac{k+1}{k} = \frac{k+1}{2}$$

For the $n=2$ case, $$s_2 = 1 = \frac{2}{2}$$

By induction, $s_n = n/2$ is true for natural numbers $n\ge 2$. i.e. $$\frac{1}{n}s_n = \frac12$$


Some example of the recursion $s_{k+1} = s_k\cdot\left(1+\frac1k\right) $:

$$\begin{align*} s_4 &= 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{2\cdot3}\\ &= \left(1 + \frac{1}{2}\right) + \frac{1}{3}\left(1 + \frac{1}{2}\right)\\ s_5 &= 1 + \frac12+\frac13+\frac1{2\cdot3}+\frac14+\frac1{2\cdot4} +\frac1{3\cdot4} + \frac{1}{2\cdot3\cdot4}\\ &= \left(1 + \frac12+\frac13+\frac1{2\cdot3}\right) + \frac14\left(1 + \frac12+\frac13+\frac1{2\cdot3}\right) \end{align*}$$

$\endgroup$
9
$\begingroup$

If you factor it as $\frac{1}{n}(1+\frac{1}{2})(1+\frac{1}{3})\dots (1+\frac{1}{n-1})$ it telescopes nicely.

$\endgroup$
  • $\begingroup$ Oo, that is really nice. How does one sum that? $\endgroup$ – Dirigible May 1 '16 at 22:30
  • $\begingroup$ Well if we simplify the terms we get: $\frac{1}{n} \cdot \frac{3}{2} \cdot \frac{4}{3} \cdot \dots \cdot \frac{n}{n-1}$ and almost all the numerators and denominators cancel (this is what I meant by telescoping) and we are left with just $\frac{1}{2}$. $\endgroup$ – Nate May 2 '16 at 14:05
1
$\begingroup$

With more systematic notation, your observation is that $$ f(n) = \sum_{A\subseteq\{2,3,\ldots,n-1\}}\;\prod_{k\in A} \frac1k = \frac12n $$ (I don't see where you get "$0.5n -1$" out of it; subtracting $1$ doesn't seem to match anything in your examples.)

This does hold for all $n\ge 2$, and we can prove it by mathematical induction on $n$:

When we go from $f(n)$ to $f(n+1)$, the difference is that we now have more $A$s to sum over -- namely, we have all the ones we have before, plus all of the subsets that contain $n$. But each of the new subsets arises as one of the old subsets with $n$ appended, so we can write it as $$ \begin{align} f(n+1) &= \sum_{A\subseteq\{2,3,\ldots,n-1\}}\; \prod_{k\in A} \frac1k + \sum_{A\subseteq\{2,3,\ldots,n-1\}}\;\frac1n \prod_{k\in A} \frac1k \\ &= f(n) + \frac1n f(n) \\& = \frac{n+1}{n} f(n) \\& = \frac{n+1}{n} \frac12 n \\& = \dfrac12 (n+1) \end{align} $$ which is what is needed for the induction step.

$\endgroup$
  • $\begingroup$ The $0.5n-1$ comes from first multiplying both sides by $n$ then subtracting 1 in order to be left solely with the products on the left hand side. Your expression should have a 1+ at the beginning as it is not included in the products. Hopefully that clears my observation up a little. $\endgroup$ – Dirigible May 1 '16 at 22:29
  • $\begingroup$ @Dirigible: Subtracting $1$ will lead to results that are $1$ too small. If I had a $1+$ in front of my expressions, they would lead to results that are $1$ too large. For example, $$f(4)=\frac11+\frac12+\frac13+\frac1{2\times 3}=2=\frac12\cdot 4 $$ Subtracting $1$ would give $\frac12\cdot4-1=1$ and $1$ is not the correct result of the addition $\frac11+\frac12+\frac13+\frac16$. $\endgroup$ – hmakholm left over Monica May 2 '16 at 6:54
  • 1
    $\begingroup$ @Dirigible I think the confusion is about whether the $1$ belongs to the sum of "fractions" $f(n)$ naturally; and it belongs. For case $n=4$, the subsets of $\{2,3\}$ are $$A\in\{\emptyset,\ \{2\},\ \{3\},\ \{2,3\}\},$$ which correspond to the products $\prod_{k\in A}\frac1k$ respectively: $$1,\ \frac12,\ \frac13,\ \frac1{2\cdot3}.$$ Here, the $1$ is the empty product from an empty set. Removing the $1$ and only considering $1/2+1/3+1/(2\cdot3)$ just complicates it. $\endgroup$ – peterwhy May 2 '16 at 8:01
  • $\begingroup$ @peterwhy Yes, that is the source of the confusion. I considered 1 to be separate from the products. Could you explain a little further why 1 is the empty product? $\endgroup$ – Dirigible May 3 '16 at 13:32
  • 1
    $\begingroup$ @Dirigible It is like considering $1 = \frac1{2^0\cdot3^0}$ -- $1$ is the multiplicative identity. See Wikipedia empty product. $\endgroup$ – peterwhy May 3 '16 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.