Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.