Help with induction, please. Struggling for hours... $$\sum_{i=1}^n \frac{1}{n+i} = \sum_{i=1}^{2n} \frac{(-1)^{i+1}}{i}$$
$$\prod_{i=1}^n (1-x_i) \gt 1-\sum_{i=1}^{n} x_i$$
Can someone please help me with these two? For the first one I have never seen two variables in one induction question and for the second one I have never done anything with sigma notation, so don't know how to proceed...
Thanks!!
 A: Just change the variable. Instead of summing over $i$, sum over some variable $j=n+i$. Then the first value is going to be $n+1$ and the last value is $n+n=2n$. So you write $$\sum_{i=1}^n\frac1{n+i}=\sum_{j=n+1}^{2n}\frac1j$$
For the second part neither the product terms or the sum terms depend on $i$. So you rewrite that as $$(1-x)^n>1-nx$$
EDIT
So let's see what that means for part 1: take $n=1$. The left hand side is $$\sum_{i=1}^1\frac{1}{1+i}=\frac12$$ The right hand side is $$\sum_{i=1}^2\frac{(-1)^{i+1}}{i}=\frac{(-1)^2}{1}+\frac{(-1)^3}{2}=1-\frac12=\frac12$$
Let's try $n=2$. Left hand side is $$\sum_{i=1}^2\frac1{2+i}=\frac13+\frac14=\frac7{12}$$
Notice that I wrote this as $$\sum_{j=2+1=3}^{2\cdot2=4}\frac 1j$$
The right hand side is $$\sum_{i=1}^{2\cdot 2=4}\frac{(-1)^{i+1}}i=1-\frac12+\frac13-\frac14=\frac{12-6+4-3}{12}=\frac7{12}$$
So you equality holds for $n=1$ and $n=2$. The induction method says that if the statement holds for $n$, then it should hold for $n+1$ as well. So we know that $$\sum_{i=1}^n\frac1{n+i}=\sum_{i=1}^{2n}\frac{(-1)^{i+1}}{i}$$
We want to show that$$\sum_{i=1}^{n+1}\frac1{n+1+i}=\sum_{i=1}^{2(n+1)}\frac{(-1)^{i+1}}{i}$$
Now I'm going to use my hint and write the left hand side as $$\sum_{j=n+2}^{2n+2}\frac1j=\sum_{j=n+1}^{2n+2}\frac1j-\frac1{n+1}=\sum_{j=n+1}^{2n}\frac1j-\frac1{n+1}+\frac1{2n+1}+\frac1{2n+2}$$
Notice that I added a term at the beginning, which I had to subtract, and the last two terms I wrote them explicitly. Why this way? Because now the sum is the same as for the base case.
$$\sum_{j=n+1}^{2n}\frac1j-\frac1{n+1}+\frac1{2n+1}+\frac1{2n+2}=\sum_{i=1}^{2n}\frac{(-1)^{i+1}}i+\frac1{2n+1}-\frac1{2n+2}\\=\sum_{i=1}^{2n}\frac{(-1)^{i+1}}i+\frac{(-1)^{2n+2}}{2n+1}+\frac{(-1)^{2n+3}}{2n+2}=\sum_{i=1}^{2n+2}\frac{(-1)^{i+1}}i$$
