Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.