2
$\begingroup$

Prove by induction that the sum of harmonic series Hn from 1 to n where n is a natural number is as follows. $$ H_n = \sum\limits_{i=1}^n 1/i $$ Prove: $$ \sum\limits_{i=1}^nH_i = (n+1)H_n -n $$ n=1 $$ H_1 = 1 = (1+1)(H_1) -1 = 2(1)-1 =1 $$ n=k+1 $$ H_{n+1} = H_n +1/(n+1) $$ $$ H_1 +H_2 +... +H_{n+1} = (n+1 +1 )H_{n+1} -(n+1) $$ $$ H_1 +H_2 +... +H_{n+1} = (n+2)H_{n+1} -n -1 $$ $$ H_1 +H_2 +... +H_{n+1} = (n+2)H_{n+1} -n -1 $$ $$ H_1 +H_2 +... +H_{n+1} = nH_{n+1} +2H_{n+1} -n -1 $$ $$ H_1 +H_2 +... +H_{n} = nH_{n+1} +2H_{n+1} -n -1 = (n+2)(H_{n+1}) -n -1 $$ $$ H_1 +H_2 +... +H_{n} =(n+2)(H_n +1)/(n+1) -n -1 $$ At this point I get lost. I've been at this for a while and I don't know if I'm even on the right track, does anyone have a solution. Did I go wrong anywhere?

$\endgroup$
  • $\begingroup$ You only need to write, since $H_1=1$, that $H_1 = 2 H_1-1$, but you really need to include $2H_1-1$ for clarity. $\endgroup$ – Thomas Andrews Nov 5 '14 at 3:14
  • $\begingroup$ Induction is a good strategy. But don't assume the thing you're trying to prove ... you do that in the second line of your seven-equation group. Instead, start from $H_{n+1} = H_n + \frac1{n+1}$ and plug in the induction hypothesis for $H_n$; see if you can rewrite the resulting expression to deduce that second line (rather than assuming it). $\endgroup$ – Greg Martin Nov 5 '14 at 3:25
2
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{i\ =\ 1}^{n}H_{i} = \pars{n + 1}H_{n} - n:\ {\large ?}.\quad n\ \geq\ 1}$.

By Induction:

It's obviously true for $\ds{n = 1}$. Lets assume that it's true for a given $\ds{n\ >\ 1}$. Then, \begin{align} &\color{#c00000}{\sum_{i\ =\ 1}^{n + 1}H_{i}} =\sum_{i\ =\ 1}^{n}H_{i} + H_{n + 1} =\pars{n + 1}H_{n} - n + H_{n + 1} \\[5mm]&=\pars{n + 1}\pars{H_{n + 1} - {1 \over n + 1}} - n + H_{n + 1} =\pars{n + 1}H_{n + 1} - 1 - n + H_{n + 1} \\[5mm]&=\color{#c00000}{\bracks{\pars{n + 1} + 1}H_{n + 1} - \pars{n + 1}} \end{align}

In addittion:

The direct proof becomes: \begin{align}&\color{#66f}{\large\sum_{i\ =\ 1}^{n}H_{i}} =\sum_{i\ =\ 1}^{n}\sum_{k\ =\ 1}^{i}{1 \over k} =\sum_{k\ =\ 1}^{n}{1 \over k}\sum_{i\ =\ k}^{n}1 =\sum_{k\ =\ 1}^{n}{1 \over k}\pars{n - k + 1} =\pars{n + 1}\sum_{k\ =\ 1}^{n}{1 \over k} - \sum_{k\ =\ 1}^{n}1 \\[5mm]&=\color{#66f}{\large\pars{n + 1}H_{n} - n} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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