Let $n$ be a positive integer. Show that \begin{align*}&\quad\,\,\frac{1}{\binom{n}{1}}+\frac{1}{2\binom{n}{2}}+\frac{1}{3\binom{n}{3}}+\cdots+\frac{1}{n\binom{n}{n}}\\&=\frac{1}{2^{n-1}}+\frac{1}{2\cdot2^{n-2}}+\frac{1}{3\cdot2^{n-3}}+\cdots+\frac{1}{n\cdot2^0}.\end{align*}
Problem
Source: MOP 2005 Homework - Red Group #13
Tags: induction, algebra solved, algebra
joybangla
06.05.2014 19:24
See the sum on the LHS is $\sum_{k=1}^{n}\frac{1}{k\dbinom{n}{k}}=\sum_{k=1}\frac{1}{n\dbinom{n-1}{k-1}}$. Now this is just USA TST 2000 P4.
sayantanchakraborty
24.11.2014 05:16
Let $f(n)=\sum_{i=1}^{n}{\frac{1}{i\dbinom{n}{i}}}$ $g(n)=\sum_{i=1}^{n}{\frac{1}{i \cdot 2^{n-i}}}$ Then we have $f(n)-f(n+1)$ $=\sum_{i=1}^{n}{\frac{1}{i\dbinom{n}{i}}-\sum_{i=1}^{n+1}{\frac{1}{i\dbinom{n+1}{i}}}}$ $=\sum_{i=1}^{n}\left(\frac{1}{i\dbinom{n}{i}}-\frac{1}{(i+1)\dbinom{n+1}{i+1}}\right)-\frac{1}{n+1}$ $=\sum_{i=1}^{n}\left(\frac{1}{i\dbinom{n}{i}}-\frac{1}{(n+1)\dbinom{n}{i}}\right)-\frac{1}{n+1}$ $=\sum_{i=1}^{n}\left(\frac{1}{i \cdot \frac{n+1}{n+1-i}\dbinom{n}{i}}\right)-\frac{1}{n+1}$ $=\sum_{i=1}^{n}\left(\frac{1}{i\dbinom{n+1}{i}}\right)-\frac{1}{n+1}$ $=f(n+1)-\frac{2}{n+1}$ Thus we get $f(n+1)=\frac{f(n)}{2}+\frac{1}{n+1}$ Also note that $g(n)-g(n+1)$ $=\sum_{i=1}^{n}{\frac{1}{i \cdot 2^{n-i}}-\sum_{i=1}^{n+1}{\frac{1}{i \cdot 2^{n+1-i}}}}$ $=\sum_{i=1}^{n}\left({\frac{1}{i \cdot 2^{n-i}}-\frac{1}{i \cdot 2^{n+1-i}}\right)-\frac{1}{n+1}}$ $=\sum_{i=1}^{n}{\frac{1}{i \cdot 2^{n+1-i}}-\frac{1}{n+1}}$ $=g(n+1)-\frac{2}{n+1}$ Once again we get $g(n+1)=\frac{g(n)}{2}+\frac{1}{n+1}$. We also get $f(1)=g(1)=1$.Thus by induction $f(n)=g(n) \forall n \in \mathbb{N}$ as desired.