## windsylph Group Title Prove that the sum of n harmonic numbers H_1 + H_2 + ... + H_n = (n+1)H_n - n 2 years ago 2 years ago

1. yakeyglee Group Title

What do you define as a harmonic number? $$H_n= \frac{1}{n}$$?

2. windsylph Group Title

H_n =1+ 1/2 + 1/3 + ... 1/n

3. windsylph Group Title

H_n is the actual sum from k=1 to n of 1/k

4. Limitless Group Title

So: $H_n=\sum_{1 \leq i \leq n}\frac{1}{i}$

5. Limitless Group Title

6. windsylph Group Title

No, I'm in a Discrete Mathematics course right now. This is one of the challenge homework problems in the book.

7. Limitless Group Title

Concrete Mathematics has an entire chapter dedicated to summation. You could learn various great concepts. This is even one particular problem. I recommend the book to you. I could attempt to explain the method, if you would like. It is a weebit complex, however.

8. windsylph Group Title

I guess you could try.. the course assumes the student has a math background up to Calculus I. So far I've completed three calculus courses, ordinary differential equations, and linear algebra. Not sure if this problem pulls material from these latter courses though. Even so I doubt I'll understand what you're about to explain lol

9. windsylph Group Title

But basically, a summation of a summation, right? Although I don't think the way to approach that is basic at all haha

10. Limitless Group Title

Yes, that is step one. It requires manipulating the sum from there.

11. windsylph Group Title

$\sum_{j=1}^{n} H_n = \sum_{j=1}^{n} \sum_{k=1}^{j} \frac{1}{k}$ Lol, what's next?

12. Limitless Group Title

Wait, first. Do you know what the Iverson Bracket is?

13. windsylph Group Title

idk if I even typed that right.. aside from indexing errors

14. windsylph Group Title

Sorry, but no

15. Limitless Group Title

It's okay. Not many people do. But it is a notation used in summation to make things easier. The idea is this: $[x]= \left\{ \begin{array}{c} 1 &\text{if } x \text{ is true},\\ 0 &\text{otherwise.} \end{array} \right.$

16. Limitless Group Title

Okay, so this is relevant because it allows summation to be manipulated easily. When we say, for example, $$\sum_{1 \leq i \leq n}i$$, we can equivalently say (using this notation) $\sum_{i} i [1\leq i \leq n]$ This works because we take $$i$$ to be evaluated from $$-\infty$$ to $$\infty$$ and the Iverson Bracket is zero at all points which do not satisfy our condition. Make sense?

17. Limitless Group Title

(Oh, by the way, $$\sum_{1 \leq i \leq n}i$$ is the same as $$\sum_{i=1}^{n}i$$.)

18. windsylph Group Title

actually.. we may actually be able to prove it without using that. the chapter I'm working on is about proofs by induction. a simple algebraic manipulation may work

19. Limitless Group Title

Ah, yes. Induction is much easier. But this makes sense of _why_ it is how it is.

20. Limitless Group Title

For induction, check $$n=1$$. Then, assume for some integer $$k$$, that the statement is true. Show that by adding $$H_{k+1}$$ to the left side results in the right side.

21. windsylph Group Title

Haha thanks.. Sorry for the trouble. Maybe I should've mentioned induction earlier

22. Limitless Group Title

No, it's fine. You should learn about Iverson Brackets and etc anyway. Trust me, it makes almost every summation ridiculously easier.

23. windsylph Group Title

Thanks, that might help in later computer science classes. The course I'm taking right now is like discrete math for comp sci

24. Limitless Group Title

Concrete Mathematics is all about Discrete Mathematics. Take a look here on Wiki about it: http://en.wikipedia.org/wiki/Concrete_Mathematics

25. windsylph Group Title

Oh wow, then I might really come across it in my later years of study. Thank you very much for the info!

26. Limitless Group Title

You're welcome. :D