# induction with sequences

I'm having a lot of trouble with this induction problem. We have a sequence of numbers defined by $X_i = \sum_{j=1}^i \frac{1}{j}$. The objective is, if we have an integer $i>1$, to show that $\sum_{j=1}^{i-1} X_j = iX_i - i$

-
So far I have, by induction, that $\sum_{j=1}^{i} X_j = iX_i - i$. Then I have $\sum_{j=1}^{i} X_j=\sum_{j=1}^{i-1} X_j +\sum_{j=i}^{i} X_j$, where the first term uses the inductive assumption. But after this, I've hit a wall – johnnymath Oct 12 '11 at 0:59

Let’s get the induction off the ground first. The smallest value of $i$ for which the result is supposed to hold is $i=2$; is it true that $\sum_{j=1}^{2-1}X_j = 2X_2-2$? $\sum_{j=1}^{2-1}X_j = X_1 = 1$, and $2X_2-2 = 2(1+1/2)-2=1$, so the base of the induction is okay.
Now for your induction step you want to assume that $$\sum_{j=1}^{i-1}X_j = iX_i-i$$ and try to prove the next case, i.e., that $$\sum_{j=1}^{(i+1)-1}X_j = (i+1)X_{i+1}-(i+1)$$ or, more simply, that $$\sum_{j=1}^iX_j=(i+1)X_{i+1}-i-1.\tag{1}$$
Now split the left-hand side of $(1)$ so as to be able to use the induction hypothesis: \begin{align*} \sum_{j=1}^iX_j &= \sum_{j=1}^{i-1}X_j + X_i\\ &= iX_i - i + X_i\tag{by the induction hypothesis}\\ &= (i+1)X_i - i.\tag{2} \end{align*}
Now $(2)$ isn’t quite what you want, but it looks enough like $(1)$ to offer a reasonable hope that it can be manipulated into the desired form. In fact that’s very easy to do: try simplifying the right-hand side of $(1)$ to get $(2)$.