# Logarithmic approximation of $\sum_0^{N-1} \frac{1}{2i + 1}$

Can anyone confirm that it's possible to approximate the sum $\sum_0^{N-1} \frac{1}{2i + 1}$ with the $\frac{\log{N}}{2}$? And why?

It's clearly visible that the sum has a logarithmic growth over i (check wolphram) but it's unclear to me how to prove it.

$\newcommand{\+}{^{\dagger}}% \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{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \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{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \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]{\,#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}$ \begin{align} \sum_{i = 0}^{N - 1}{1 \over 2i + 1}&=\half\sum_{i = 0}^{N - 1}{1 \over i + 1/2} = \half\bracks{\Psi\pars{\half + N} - \Psi\pars{\half}} = \half\Psi\pars{N + \half} + \half\,\gamma + \ln\pars{2} \end{align} where $\Psi\pars{z}$ is the $\it\mbox{digamma function}$ and $\gamma = 0.577215664901533\ldots$ is the $\it\mbox{Euler-Mascheroni constant}$. $\ds{\Psi\pars{1 \over 2} = -\gamma - 2\ln\pars{2}}$

Also, $\ds{\Psi\pars{z} \approx \ln\pars{z} - {1 \over 2z}\ \mbox{when}\ \verts{z} \gg 1}$: \begin{align} \sum_{i = 0}^{N - 1}{1 \over 2i + 1} &\approx \half\bracks{\ln\pars{N + \half} - {1 \over 2\pars{N + 1/2}}} + \half\,\gamma + \ln\pars{2}\,, \qquad N \gg 1 \end{align} $$\color{#0000ff}{\large% \sum_{i = 0}^{N - 1}{1 \over 2i + 1} \approx \half\ln\pars{N + \half} - {1 \over 2\pars{2N + 1}} + \half\,\gamma + \ln\pars{2}\,, \quad N \gg 1}$$ $\large{\bf ADDENDUM:}$ Following $\tt @Matteo$ comment:

Also, \begin{align} \half\sum_{i = 0}^{N - 1}{1 \over i + 1/2} &=\half\sum_{i = 0}^{N - 1}\pars{{1 \over i + 1/2} - {1 \over i + 1}} + \half\bracks{\sum_{i = 0}^{N - 1}{1 \over i + 1} - \ln\pars{N}} + \half\,\ln\pars{N} \\[3mm]&={1 \over 4}\sum_{i = 0}^{N - 1}{1 \over \pars{i + 1}\pars{i + 1/2}} + \half\bracks{\sum_{i = 0}^{N - 1}{1 \over i + 1} - \ln\pars{N}} + \half\,\ln\pars{N} \\[3mm]&\stackrel{N\ \gg\ 1}{\ds{\LARGE\sim}} {1 \over 4}\,{\Psi\pars{1} - \Psi\pars{1/2} \over 1 - 1/2} + \half\,\gamma + \half\,\ln\pars{N} \\[3mm]&= \half\braces{-\gamma - \bracks{-\gamma - 2\ln\pars{2}}} + \half\,\gamma + \half\,\ln\pars{N} \\[3mm]&=\color{#0000ff}{\large\half\,\ln\pars{N + \half} - {1 \over 2\pars{2N + 1}} + \half\,\gamma + \ln\pars{2}} \\[3mm]&\phantom{=}+ \color{#ff0000}{\underbrace{\half\bracks{% {1 \over 2N + 1} - \ln\pars{1 + {1 \over 2N}}}} _{\sim\ {\rm O}\pars{1/N^{2}}}} \end{align}
• I suppose that you have a typo in the last (blue) equation : 2(N+1/2) = (2N+1) and not 2(2N+1). Cheers. Jan 9, 2014 at 5:34
• @ClaudeLeibovici There is an extra factor $2$ due to the $1/2$ factor in front of the previous bracket $[]$. Jan 9, 2014 at 5:37
• Oooops ! Sorry for that stupidity ! Cheers. Jan 9, 2014 at 5:40
• Felix, could you please explain me the passage from summation to digamma function? Thanks in advance Jan 9, 2014 at 23:15
• @Matteo I found that expression in Gradshteyn and Ryzhik Table ( 7$^{\underline{\rm a}}$ ed. page 904. Formula ${\bf 8.365}.3$ ). It's exactly written in the form $\displaystyle{\large\Psi\left(x + n\right) = \Psi\left(x\right) + \sum_{k = 0}^{n - 1}{1 \over x + k}}$. However, I'll put and ADDENDUM to the answer in a few minutes. Jan 9, 2014 at 23:36

This is a Riemann sum for the integral from 0 to $N$ of $1/(2x+1)$, so it approximates $(1/2)\ln(2N+1)$, which is approximately $(1/2)\ln N$.

• I see, thanks. Could you please explain also why the Riemann sum approximates $(1/2)\ln(2N+1)$? Jan 9, 2014 at 3:20
• Because that is the solution to the integral, and Riemann sums always approximate the actual integral. The Euler-Mascheroni constant indirectly measures how close this particular sum is (you should look it up on Wikipedia, it is very interesting). Jan 9, 2014 at 3:39