search
Log In
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
35 votes
2.1k views

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
2.1k views
6
\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$
0
wonderful Question !
0
present in current syllabus?

2 Answers

71 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
7
Take n =2 and then find first two harmonic numbers.

And then find their sum.And then use options/only b will satisfy:)
1
Is both B) and D) are correct answers ...?
0
With this method, none of the options are matching....... I'm getting 5/2 for both B and D, instead of 3/2, when n=2
1
For such questions, it's fast to check using specific values.

Consider n=4

H1=1

H2=3/2

H3=11/6

H4=25/12

H(n+1) i.e. H5=137/15

Summation of H1 till H4 is 77/12 which is only given by option (b).

Hence, the answer.
0

Ayush Upadhyaya 

G5= 137/60 and for n=4,77/12 both b and d will satisfy

n=2,3,4,5 i tried and both b and d are satisfied.I dont think we can use this approach.Earlier i used this approach but i approximated 1/3 in calc but if i dont than both b and d are giving same answer always from n=2 to 6.

6

In the continuation to above proof, from last line of the proof in he given answer to show that it is equal to D also.SO bith B and D are true here.

0
nice explanation @ pragy agrawal sir
0
That is right you have to take sum of first  two terms not the term itself
0
I guess both B & D are correct. Please update the answer as B & D.
0

$D$ also true for every case.

Example:

$H_{1}+H_{2}+H_{3}+H_{4}+H_{5}=1+\dfrac{3}{2}+\dfrac{11}{6}+\dfrac{25}{12}+\dfrac{137}{60}=\dfrac{522}{60}=\dfrac{87}{10}$

$H_{6}=\dfrac{147}{60}$

$D)\ 6*H_{6}-6=6*\dfrac{147}{60}-6=\dfrac{87}{10}$


Can try for other values also. If got something which is proving D as wrong. Do tell.

–4 votes

The correct answer is, (B) (n + 1)Hn - n

Answer:

Related questions

14 votes
4 answers
1
1.4k views
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. ... $\text{P-III, Q-II, R-IV, S-I}$ $\text{P-IV, Q-II, R-I, S-III}$
asked Nov 2, 2014 in Algorithms Ishrat Jahan 1.4k views
31 votes
11 answers
2
4.4k views
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
asked Nov 2, 2014 in Combinatory Ishrat Jahan 4.4k views
18 votes
4 answers
3
1.9k views
Consider the sequence $\langle x_n \rangle , \: n \geq 0$ defined by the recurrence relation $x_{n+1} = c . x^2_n -2$, where $c > 0$. Suppose there exists a non-empty, open interval $(a, b)$ such that for all $x_0$ satisfying $a < x_0 < b$, the sequence converges to a limit. The sequence converges to the value? $\frac{1+\sqrt{1+8c}}{2c}$ $\frac{1-\sqrt{1+8c}}{2c}$ $2$ $\frac{2}{2c-1}$
asked Oct 31, 2014 in Combinatory Ishrat Jahan 1.9k views
2 votes
1 answer
4
705 views
Given below are several usages of the anchor tag in HTML. <A HREF = "http://www.gate.ac.in/HTML/BASIC/testpage.html">Test Me</A> <A HREF = "/BASIC/testpage.html">Test Me</A> <A HREF = "testpage.html">Test Me</A> <A HREF = "testpage.html#test">Test Me</A> Which of the above are valid? I and II only I and III only I, II and III only I, II, III and IV
asked Nov 2, 2014 in Web Technologies Ishrat Jahan 705 views
...