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$
induction with sequences
-
0So 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 – 2011-10-12
1 Answers
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)$.