7

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.

Nikunj
  • 6,160
Dirigible
  • 73

3 Answers3

9

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.

Nate
  • 11,206
  • Oo, that is really nice. How does one sum that? – Dirigible May 01 '16 at 22:30
  • 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}$. – Nate May 02 '16 at 14:05
1

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.

hmakholm left over Monica
  • 286,031
  • 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. – Dirigible May 01 '16 at 22:29
  • @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$. – hmakholm left over Monica May 02 '16 at 06:54
  • 1
    @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. – peterwhy May 02 '16 at 08:01
  • @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? – Dirigible May 03 '16 at 13:32
  • 1
    @Dirigible It is like considering $1 = \frac1{2^0\cdot3^0}$ -- $1$ is the multiplicative identity. See Wikipedia empty product. – peterwhy May 03 '16 at 13:39
  • @Henning Makholm My conversation with peterwhy cleared things up. Thanks, Henning! – Dirigible May 03 '16 at 14:00
1

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*}$$

peterwhy
  • 22,256