in Combinatory edited by
5,548 views
41 votes
41 votes

Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$,  $\sum_{j=1}^{n} H_j$ can be expressed as

  1. $nH_{n+1} - (n + 1)$
  2. $(n + 1)H_n - n$
  3. $nH_n - n$
  4. $(n + 1) H_{n+1} - (n + 1)$
in Combinatory edited by
5.5k views

3 Comments

\begin{array}{c c c}
H_{1} &= &\frac{1}{1} &&&&&(+)\\
H_{2} &= &\frac{1}{1} &+ &\frac{1}{2}&&&(+) \\
H_{3} &= &\frac{1}{1} &+ &\frac{1}{2} &+ &\frac{1}{3}&\\
\hline
 4*H_3&=& \frac{1}{1} &+ &\frac{1}{2} &+ &\frac{1}{3}&(+)\\
&& \frac{1}{1} &+ &\frac{1}{2} &+ &\color{red}{\frac{1}{3}}&(+)\\
 &&\frac{1}{1} &+ &\color{red}{\frac{1}{2}} &+ &\color{red}{\frac{1}{3}}&(+)\\
&&\color{red}{\frac{1}{1}} &+ &\color{red}{\frac{1}{2}} &+ &\color{red}{\frac{1}{3}}&\\
\hline
(3+1)*H_3&=& \color{red}{1}+\frac{1}{1}*3 &+&\color{red}{1}+\frac{1}{2}*2&+&\color{red}{1}+\frac{1}{3}*1 &= S_3 +\color{red}{3}\\
\hline
\end{array}
So, $S_n= (n+1)H_n - n$
7
7
wonderful Question !
0
0
present in current syllabus?
0
0

1 Answer

102 votes
102 votes
Best answer

The $n^{th}$ Harmonic Number  is defined as the summation of the reciprocals of all numbers from $1$ to $n$.

$$H_n = \sum_{i = 1}^n \frac1 i = \frac1 1 + \frac1 2 + \frac1 3 + \frac1 4 + \dots + \frac1 n$$

Lets call the value of $\sum_{j = 1}^n H_j$ as $S_n$

Then,

$\begin{align}
S_n &= H_1 + H_2 + H_3 + \dots + H_n\\[1em]
&= \small \overbrace{\left ( \color{red}{\frac1 1} \right )}^{H_1}
 + \underbrace{\left (\color{red}{\frac1 1} + \color{blue}{\frac1 2} \right )}_{H_2}
 + \overbrace{\left (\color{red}{\frac1 1} + \color{blue}{\frac1 2} + \color{green}{\frac1 3} \right )}^{H_3}
 + \dots
 + \underbrace{\left (\color{red}{\frac1 1} + \color{blue}{\frac1 2} + \color{green}{\frac1 3} + \dots + \frac1 n \right )}_{H_n}\\[1em]
&=\small  \color{red}{n \times\frac1 1}+ \color{blue}{ (n-1) \times\frac1 2} + \color{green}{(n-2) \times \frac1 3} + \dots + 1 \times \frac1 n\\[1em]
&= \sum_{i = 1}^n \left (n - i + 1 \right ) \times \frac1 i\\[1em]
&= \sum_{i = 1}^n \left ( \frac{n + 1}{i} - 1 \right )\\[1em]
&= \left ( \sum_{i = 1}^n \frac{\color{red}{n+1}}{i}\right ) - \color{blue}{\left ( \sum_{i = 1}^n 1\right )}\\[1em]
&= \left (\color{red}{(n+1)} \times \underbrace{\sum_{i = 1}^n \frac1 i}_{=H_n}\;\right ) - \color{blue}{n}\\[3em]
\hline
\large S_n &= \large (n+1)\cdot H_n - n
\end{align}$

Hence, the answer is option (B).

edited by

4 Comments

Nice explanation
1
1

option (D) does not satisfy in every case. Check for $S_{3}$, it doesn’t satisfy. According to opt. D, $S_{3}$=$\frac{63}{3}$ but according to the summation series $S_{3}$=$\frac{26}{6}$.

0
0
Option D will also give $26/6.$ Proof does not tell a lie.

Proof provided by Rahul Sharma is correct and so both options B and D are correct.

Option D or similar to D is given in Knuth’s concrete maths book.
0
0
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true