# Prove that the sum of harmonic series 1..n can be expressed as (n+1)H_n -n

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?

• 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. – Thomas Andrews Nov 5 '14 at 3:14
• 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). – Greg Martin Nov 5 '14 at 3:25

## 1 Answer

$\newcommand{\angles}{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}{\left(\, #1 \,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}} \newcommand{\verts}{\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}