We prove by induction on $n$. Denote the left hand side by $a_n$, and the right hand side by $b_n$. Clearly, $a_0 = b_0 = 1$. Now assume that $a_{n-1} = b_{n-1}$, we shall prove that $a_n = b_n$. \begin{eqnarray*} b_n &=& \frac{n+1}{2^{n+1}} (\frac{2}{1} + \frac{2^2}{2} +\dots+ \frac{2^n}{n} + \frac{2^{n+1}}{n+1}) = \frac{n+1}{2n}\frac{n}{2^{n}} (\frac{2}{1} + \frac{2^2}{2} +\dots+ \frac{2^n}{n}) + 1 \\ &=& \frac{n+1}{2n} b_{n-1} + 1 =\frac{n+1}{2n} a_{n-1} + 1. \end{eqnarray*} Now, \begin{eqnarray*} \frac{n+1}{2n} a_{n-1} + 1 &=& 1 + \frac{n+1}{2n}\sum_{i=0}^{n-1}\frac{i! (n-1-i)!}{(n-1)!} = 1 + \frac{1}{2}\sum_{i=0}^{n-1}\frac{((i+1) + (n-i) ) \cdot i! (n-1-i)!}{n\cdot(n-1)!} \\ &=& 1 + \frac{1}{2}\sum_{i=0}^{n-1}\frac{(i+1)!(n-1-i)! +i! (n-i)}{n!} = 1 + \frac{1}{2}\left( \sum_{i=1}^n \binom{n}{i}^{-1} + \sum_{i=0}^{n-1} \binom{n}{i}^{-1}\right) \\ &=&\sum_{i=0}^n \binom{n}{i}^{-1}. \end{eqnarray*}

,due to cecil,the proposer,there is sol,using nth dimensional cube and resistor arrangement configuration,which seems very stange you can find it in mathematical olyppiad challenges-titu,razvan. anyway its standard using induction,provided you dont loose hope

An application of this problem http://www.artofproblemsolving.com/Forum/viewtopic.php?f=586&t=290285 who wrote: ,due to cecil,the proposer,there is sol,using nth dimensional cube and resistor arrangement configuration,which seems very stange you can find it in mathematical olyppiad challenges-titu,razvan. anyway its standard using induction,provided you dont loose hope Original problem from Kvant (Prof.Titu said it in his book-Problems from the book)

From the beta function (or just induction and integration by parts), we have \begin{align*} \sum_{k=0}^{n}\binom{n}{k}^{-1} &= (n+1)\sum_{k=0}^{n}\frac{k!(n-k)!}{(n+1)!}\\ &= (n+1)\int_{0}^{1}\sum_{k=0}^{n}x^k(1-x)^{n-k}\;dx\\ &= (n+1)\int_{0}^{1}\frac{(1-x)^{n+1}-x^{n+1}}{1-2x}\;dx. \end{align*}We can now induct on $n$. The base case $n=0$ is obvious, so it suffices to show that \[\frac{1}{2^n}\frac{2^{n+1}}{n+2}=\int_{0}^{1}\frac{(1-x)^{n+1}(2(1-x)-1)-x^{n+1}(2x-1)}{1-2x}\;dx.\]But \begin{align*} \int_{0}^{1}\frac{(1-x)^{n+1}(2(1-x)-1)-x^{n+1}(2x-1)}{1-2x}\;dx &= \int_{0}^{1}(1-x)^{n+1}+x^{n+1}\;dx\\ &= \left[-\frac{1}{n+2}(1-x)^{n+2}+\frac{1}{n+2}x^{n+2}\right]_{0}^{1}\\ &= \frac{2}{n+2}, \end{align*}as desired.

I just realized that induction is unnecessary. Indeed, \begin{align*} I_1=\frac{2^{n+1}}{n+1}\sum_{j=0}^{n}\frac{j!(n-j)!}{n!} &=2^{n+1}\int_{0}^{1}\sum_{j=0}^{n}x^j(1-x)^{n-j}\;dx \\ &=2^{n+1}\int_{0}^{1}\frac{x^{n+1}-(1-x)^{n+1}}{x-(1-x)}\;dx, \end{align*}while \[I_2=\sum_{k=1}^{n+1}\frac{2^k}{k}=2\int_{0}^{1}\sum_{k=1}^{n+1}(2x)^{k-1}\;dx=2\int_{0}^{1}\frac{(2x)^{n+1}-1}{2x-1}\;dx.\]Thus \[I_2-I_1=2\int_{0}^{1}\frac{2^n(x^{n+1}+(1-x)^{n+1})-1}{2x-1}\;dx=0,\]where we have used the fact that \[f(x)=\frac{2^n(x^{n+1}+(1-x)^{n+1})-1}{2x-1}\]is symmetric about the point $(1/2,0)$ (expanding out $f$ we also have that $f(1/2)=0$, so this is not an issue).

Here is a solution using generating functions. Let $a_n=\frac{n+1}{2^{n+1}} \left(\frac{2}{1}+\frac{2^2}{2}+\cdots + \frac{2^{n+1}}{n+1}\right)$. Then its pretty clear that $a_n$ satisfies the recursion $2(n+1)a_{n+1}=(n+2)a_n+2(n+1)$. Thus, if we let $b_n=\sum_{i=0}^n \binom{n}{i}^{-1}$, we want to show $2(n+1)b_{n+1}=(n+2)b_n+2(n+1)$. Note $n!b_n=\sum_{i+j=n} i!j!$. Thus, we define $F(x)=\sum_{n\ge 0} n!x^n$. Then $n!b_n$ is the coefficient of $x^n$ of $F(x)^2$. Let $f(x)[j]$ denote the coefficient of $x^j$ of a general function $f$. We want to show $$2F(x)^2[n+1]=2(n+1)!+(n+2)F(x)^2[n]$$ Note $2(n+1)!=2F(x)[n+1]$. Thus we want to show $2F(x)^2-2F(x)[n+1]=(n+2)xF(x)^2[n+1]$. Note that $(n+2)g(x)[n+1]=(xg(x))'[n+1]$, so we want to show $$2F(x)^2-2F(x)[n+1]=(F(x)^2x^2)'[n+1]$$ In general, this means we want to prove the identity $$2F(x)^2-2F(x)=2F(x)F'(x)x^2+2xF(x)^2$$ or $F(x)-1=F'(x)x^2+xF(x)$, or $$F(x)(1-x)=F'(x)x^2+1$$ We can verify that for $n\ge 2$, the coefficient of $x^n$ on both sides is $(n-1)\cdot (n-1)!$, and modulo $x^2$ both polynomials are $1$.

The $n$-dimensional resistor problem came up in a physics class I take so I might as well share the physical solution, which is quite fascinating. E&M wrote: In an $n$-dimensional cube, there is a resistor of resistance 1 ohm on each edge. Compute the effective resistance between $A=(0,0,\ldots, 0)$ and $P=(1,1,\ldots,1)$. We compute said resistance in two different ways using physics and we equate the resulting expressions to prove the given identity (which finally gives a higher reason to the truth of this weird identity!) Method 1: We can group resistors in layers depending on their "distance" from the origin. Let the vertices with $k$ ones and $n-k$ zeros be "layer $k$". By symmetry, all these vertices have the same potential, so we can collapse them into a single vertex (the "bridge building" trick). Thus we have $n$ layers of parallel resistors, each contributing $\frac{1}{\dbinom{n}{k}(n-k)}$ by Kirchoff's Law, for a total of $R_n=\frac1n\sum_{i=0}^{n-1}\dbinom{n-1}{k}^{-1}$. Method 2: We want to compute the resistance by injecting a fictitious current, so we are motivated to relate this to smaller versions of the problem by pulling out the current at different points. We can do it like so: Consider the two $n-1$ dimensional cubes given by $\{(x_1,x_2,\ldots,x_{n-1},0)\}$ and $\{(x_1, x_2, \ldots, x_{n-1},1)\}$ where each $x$ is $0$ or $1$. Furthermore let $C=(0,0,\ldots, 0,1)$ and $D=(1,1,\ldots,1,0)$ be two diametrically opposite points, each on a different smaller cube. Take $B$ as the ground and we inject a current of 1 ampere at $A$. Let $V_n$ be the potential at $A$ We first notice that, by symmetry, the current leaving $A$ is spread onto its $n$ adjacent neighbours and likewise for the currents entering $B$. Thus, the potentials at $C$ and $D$ are $V_n-\frac1n$ and $\frac1n$ respectively. Similarly, if we inject a current at $C$ and take $D$ as the ground, the potentials at $A,B,C,D$ will be $V_n-\frac1n, \frac1n, V_n, 0$ respectively. By superimposing the two configurations (inject at $A$, $C$, exit at $B,D$), we get the effective potential of $A$ above $D$ is $2V_n-\frac2n$. We compute the potential of $A$ over $D$ with another argument: by symmetry, each vertex on a $n-1$ dimensional cubes and its corresponding vertex on the other one have no net current. Thus, it's as if there were no connection between the two cubes, so the potential of $A$ above $D$ is the same as the $n-1$ dimensional case of the problem, which would be $V_{n-1}$. Thus we have the recursion $2V_n-\frac2n=V_{n-1}$. Solving, we have $V_n=\sum_{i=1}^n\frac{1}{i2^{n-i}}$. By Ohm's Law, $V=RI$, but $I=1$, so $R_n=V_n$. Equating the two quantities, we get the desired proof of the given identity.

Consider a different inductive proof: Lemma 1: $\sum_{k=0}^{n} \frac{k}{\binom{n}{k}}=\frac{n}{2}\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$. $\emph{Proof: }$ Since $\binom{n}{k}=\binom{n}{n-k}$, we have \begin{align*}\sum_{k=0}^{n} \frac{k}{\binom{n}{k}}&=\sum_{k=0}^{\lfloor n/2 \rfloor}\frac{k}{\binom{n}{k}}+\frac{n-k}{\binom{n}{n-k}}\\&=\sum_{k=0}^{\lfloor n/2 \rfloor}\frac{n}{\binom{n}{k}}\\&=\frac{n}{2}\sum_{k=0}^{n}\frac{1}{\binom{n}{k}},\end{align*} as desired. $\square$ Lemma 2: $\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}=\frac{n+1}{2n} \left(\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}}\right).$ $\emph{Proof: }$ Using some elementary factoring, we have: \begin{align*}\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}&=\sum_{k=0}^{n-1}\frac{1}{\frac{n}{n-k}\binom{n-1}{k}}\\&=\sum_{k=0}^{n-1}\frac{\frac{n-k}{n}}{\binom{n-1}{k}}\\&=\sum_{k=0}^{n-1}\frac{1-\frac{k}{n}}{\binom{n-1}{k}}\\&=\left(\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}}\right)+\frac{1}{n}\left(\sum_{k=0}^{n-1}\frac{k}{\binom{n-1}{k}}\right).\end{align*} Using lemma 1, the above simplifies to \begin{align*}&\left(\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}}\right)+\frac{n-1}{2n}\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}}\\&=\frac{n+1}{2n}\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}},\end{align*} as desired. $\square$ At this point, we proceed by induction on $n$. As a base case for $n=1$, we have $\frac{1}{\binom{1}{1}}=1=\frac{2}{2^2}\cdot \frac{2}{1}$ as desired. Proceeding to the inductive step, we assume for some $n=k\geq 1$ that $\sum_{j=0}^{n}\frac{1}{\binom{k}{j}}=\frac{k+1}{2^{k+1}}\sum_{j=0}^{k}\frac{2^j}{j}$, and we show that this is also the case for $n=k+1$: By lemma 1, we have \begin{align*}\sum_{j=0}^{k+1}\frac{1}{\binom{k+1}{j}}&=\frac{k+2}{2(k+1)}\sum_{j=0}^{k}\frac{1}{\binom{k}{j}}\\ &=\frac{k+2}{2(k+1)}\cdot \frac{k+1}{2^{k+1}}\sum_{j=0}^{k}\frac{2^j}{j}\quad \text{by the inductive hypothesis}\\&=\frac{k+2}{2^{k+2}}\sum_{j=0}^{k}\frac{2^j}{j}, \end{align*} which completes the inductive step. Hence, we are done. $\blacksquare$

The crux of this problem is noting that if $S_n$ is the LHS, then we can rewrite $$2S_{n+1}=2\sum_{k=0}^{n+1} \frac{k!(n+1-k)!}{(n+1)!}=2+\frac{1}{n+1}\sum_{k=0}^{n} 2\frac{k!(n-k)!}{n!} (n+1-k)=2+\frac{1}{n+1}\left(\sum_{k=0}^{n} \frac{k!(n-k)!}{n!} (n+1-k)+\sum_{k=0}^{n} \frac{k!(n-k)!}{n!} (k+1)\right)=2+\frac{n+2}{n+1}S_n$$after which the result is easy by induction

Similar to math154's second solution, but who cares Recall from the beta integral that \[ \binom{n}{k}^{-1} = \frac{k!(n-k)!}{n!} = (n+1)\int_0^1t^k(1-t)^{n-k}\,dt, \]and so \begin{align*} \sum_{k=0}^n\binom nk^{-1} &= (n+1)\int_0^1\sum_{k=0}^nt^k(1-t)^{n-k}\,dt = (n+1)\int_0^1(1-t)^n\sum_{k=0}^n\left(\frac{t}{1-t}\right)^k\,dt\\ &= (n+1)\int_0^1(1-t)^n\left(\frac{1 - (\frac{t}{1-t})^{n+1}}{1 - \frac{t}{1-t}}\right)\,dt = (n+1)\int_0^1\frac{(1-t)^{n+1} - t^{n+1}}{1-2t}\,dt. \end{align*}Furthermore, \[ \frac{n+1}{2^{n+1}}\sum_{k=0}^n\frac{2^{k+1}}{k+1} = \frac{n+1}{2^{n+1}}\int_0^1\sum_{k=0}^n2^{k+1}t^k\,dt = \frac{n+1}{2^n}\int_0^1\frac{1-(2t)^{n+1}}{1-2t}\,dt. \]By substituting these integral representations into the original equality, it suffices to show that \[ \int_0^1\frac{(1-t)^{n} - t^{n}}{1-2t}\,dt = \frac{1}{2^{n-1}}\int_0^1\frac{1-(2t)^n}{1-2t}\,dt\qquad(*) \]for each positive integer $n$. This is surprisingly tricky. The motivation is to observe that the right hand integrand in $(*)$ has a singularity at $t = \tfrac12$, hence can be written as the sum of two integrals \begin{align*} &\;\;\;\;\int_0^{1/2}\frac{1-(2t)^n}{1-2t}\,dt + \int_{1/2}^1\frac{1-(2t)^n}{1-2t}\,dt\\ &= \int_0^{1/2}\frac{1-(2t)^n}{1-2t}\,dt + \int_{0}^{1/2}\frac{1-(2(1-t))^n}{2t-1}\,dt\\ &= 2^n\int_0^{1/2}\frac{(1-t)^n - t^n}{1-2t}\,dt. \end{align*}But observe that the new integrand is symmetric about $t = \tfrac12$. Thus, this integral also equals $2^{n-1}\textstyle\int_0^1\tfrac{(1-t)^n-t^n}{1-2t}\,dt$, which, upon dividing by $2^{n-1}$, is precisely the left hand side of $(*)$.

What's up with the calculus? For $n=1$, the result is trivial, so assume $n\ge 2$. We induct on $n$. Observe that for $1\le k\le n-1$, we have \[\binom{n}{k}^{-1} = k\cdot \binom{n-1}{k-1}^{-1} = (n-k)\cdot \binom{n-1}{k}^{-1}.\]By the induction hypothesis, we may write \[\binom{n}{0}^{-1} + \binom{n}{1}^{-1} + \cdots + \binom{n}{n}^{-1} = 2 + \sum_{k=1}^{n-1} \binom{n}{k}^{-1}=2 + \frac 1{2n}\sum_{k=1}^{n-1} \left[k\cdot \binom{n-1}{k-1}^{-1} + (n-k)\cdot \binom{n-1}{k}^{-1}\right] = \]\[2 + \frac 1{2n} \left[2 + (n+1)\sum_{k=1}^{n-2} \binom{n-1}{k}^{-1}\right] =1+\frac{n+1}{2n}\left[2+\sum_{k=1}^{n-2} \binom{n-1}{k}^{-1}\right] = \]\[1 + \frac{n+1}{2n}\cdot \frac{n}{2^n}\left(\frac 21 + \frac{2^2}2 + \cdots + \frac{2^n}{n}\right) = 1 + \frac{n+1}{2^{n+1}}\left(\frac 21 + \frac{2^2}2 + \cdots + \frac{2^n}{n}\right) = \frac{n+1}{2^{n+1}} \left( \frac{2}{1} + \frac{2^2}{2} + \cdots + \frac{2^{n+1}}{n+1} \right).\]We are done.

Here's a combinatorial solution that looks a lot like the E&M solution probably because Markov Chain transitions look pretty similar to Kirchhoff's Laws. Problem wrote: On the hypercube $\{0, 1\}^n$, two length $n$ paths traveling along the edges from $(0, 0, \ldots, 0)$ to $(1, 1, \ldots, 1)$ are selected uniformly at random. Find the expected number of vertices that they share. Approach 1: For each $0 \le k \le n$, there are exactly $\tbinom nk$ points $(x_1, x_2, \ldots, x_n)$ on the hypercube with $x_1 + x_2 + \ldots + x_n = k$, and there is an equal probability that a length $n$ path from $(0, 0, \ldots, 0)$ to $(1, 1, \ldots, 1)$ passes through any one of them (clearly it must pass through exactly one of them). Thus, the two paths intersect on the plane $x_1 + x_2 + \ldots + x_n = k$ with probability $\tbinom nk^{-1}$, i.e. \[ \mathbb E[\text{intersections}] = \sum_{k=0}^n \mathbb P [\text{intersect on } x_1 + x_2 + \ldots + x_n = k] = \sum_{k=0}^n \binom nk^{-1}. \] Approach 2: Let $A_n$ be the answer. Clearly the two paths always share the point $(0, 0, \ldots, 0)$; for the rest of the points, we casework on the second vertex of the two paths: Case 1: they are the same. There is a $\tfrac1n$ chance that this happens. The rest of the paths start and end on opposite vertices of a $(n-1)$-dimensional hypercube, so they intersect an expected $A_{n-1}$ times. Case 2: they are different. There is a $\tfrac{n-1}n$ chance that this happens. WLOG assume that the first path's second vertex is $(1, 0, 0, \ldots, 0)$ and the second path's second vertex is $(0, 1, 0, \ldots, 0)$. Then consider the paths induced on an $(n-1)$-hypercube by ignoring the first and second coordinates of the first and second paths, respectively. They intersect an expected $A_{n-1}$ times, and our original paths intersect when and only when these induced paths intersect at a point with first coordinate is $1$ (since both the first and second coordinate must be $1$ for the original paths starting at $(1, 0, 0, \ldots, 0)$ and $(0, 1, 0, \ldots, 0)$ to intersect). But on average half of the intersections of two randomly chosen length $n-1$ paths from $(0, 0, \ldots, 0)$ to $(1, 1, \ldots, 1)$ on $\{0, 1\}^{n-1}$ will have first coordinate $1$ (this is by symmetry under the transformation $\mathbf{x} \mapsto (1, 1, \ldots, 1) - \mathbf{x}$), so our original paths intersect an expected $\tfrac12 A_{n-1}$ times. It follows that \[ A_n = 1 + \frac1n A_{n-1} + \frac{n-1}n \cdot \frac12 A_{n-1} = 1 + \frac{n+1}{2n} A_{n-1} \implies \frac{A_n}{n+1} = \frac1{n+1} + \frac12 \cdot \frac{A_{n-1}}n.\]Clearly $A_1 = 2$, so \[ \frac{A_n}{n+1} = \frac1{n+1} + \frac12 \left(\frac1n + \frac12 \left( \frac1{n-1} + \left(\cdots \left( \frac13 + \frac12 \cdot \frac22 \right) \right) \right) \right) = \frac1{2^{n+1}} \left(\frac{2^{n+1}}{n+1} + \frac{2^n}n + \cdots + \frac{2^3}{3} + 2^2 \right).\]Therefore, \[ A_n = \frac{n+1}{2^{n+1}} \left( \frac{2}{1} + \frac{2^2}{2} + \cdots + \frac{2^{n+1}}{n+1} \right).\] Comparing results, we are done. $\blacksquare$

We induct on $n$; base cases are obvious. For the inductive step, we upon simplification we want to show that$$\sum_{k=1}^n \frac 1{{n \choose k}} - \frac 1{{n+1 \choose k}} = \frac n{2^{n+2}} \sum_{k=1}^{n+1} \frac{2^k}k.$$Claim. [Main Step] We have$$\frac 1{{n \choose k}} - \frac 1{{n+1 \choose k}} = \frac k{n+1} \cdot \frac 1{{n \choose k}}.$$Proof. Simply use Pascal. \begin{align*} \frac 1{{n \choose k}} - \frac 1{{n+1 \choose k}} &= \frac{{n+1 \choose k} - {n \choose k}}{{n \choose k}{n+1 \choose k}} \\ &= \frac{{n \choose k-1}}{{n \choose k}{n+1 \choose k}} \\ &= \frac{k \cdot (n-k)! k!}{(n+1)!} \\ &= \frac k{n+1} \cdot \frac 1{{n \choose k}}, \end{align*}as needed. $\blacksquare$ Now, \begin{align*} \sum_{k=0}^n \frac k{n+1} \cdot \frac 1{{n \choose k}} &= \frac 1{n+1} \sum_{k=0}^n \frac k{{n \choose k}} \\ &= \frac 1{2(n+1)} \sum_{k=0}^n \frac{k+n-k}{{n \choose k }} \\ &= \frac{n}{2(n+1)} \sum_{k=0}^n \frac 1{{n \choose k}} \\ &= \frac n{2(n+1)} \cdot \frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1} \frac{2^k}k \\ &= \frac n{2^{n+2}} \sum_{k=1}^{n+1} \frac{2^k}k, \end{align*}as required.