8
$\begingroup$

Consider the sum $$S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$$ where $0\le c\le 1$.

When $c=0$, $S(n,c)$ grows asymptotically as $n\log n$.

When $c=1$, $S(n,c)$ grows asymptotically as $n$.

What about when $0<c<1$? Can we calculate $S(n,c)$ exactly? What about asymptotics? Can we find upper/lower bounds?

$\endgroup$
  • 3
    $\begingroup$ The harmonic series grows asymptotic to $\log n-\gamma$, where $\gamma$ is the Euler-Mascheroni constant, not $n\log n$ $\endgroup$ – Tim Ratigan Dec 3 '13 at 22:43
4
$\begingroup$

We have $$S(n;c) = \sum_{k=1}^{n-1} \dfrac{k}{ck+(n-k)} = \sum_{k=1}^{n-1} \dfrac{k/n}{1+(c-1)k/n}$$ Hence, $$\dfrac{S(n;c)}n = \sum_{k=1}^{n-1} \dfrac{k/n}{1+(c-1)k/n} \dfrac1n \sim \int_0^1 \dfrac{xdx}{1+(c-1)x} = \dfrac{(c-1)-\log(c)}{(c-1)^2} \text{ for }c \in (0,1)$$ Hence, $$S(n;c) \sim \dfrac{(c-1)-\log(c)}{(c-1)^2} n \text{ for }c \in (0,1)$$ Better approximations can be obtained using Euler Maclaurin formula.

$\endgroup$
1
$\begingroup$

$\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}$ When $c = 1$, $\color{#0000ff}{\large{\rm S}\pars{n,1}} = \braces{\pars{n - 1}\bracks{\pars{n - 1} + 1}/2}/n = \color{#0000ff}{\large\pars{n - 1}/2}$.

Let's consider the case $c \not= 1$: \begin{align} {\rm S}\pars{n, c} &= \sum_{i = 1}^{n - 1}{i \over ci + \pars{n-i}} = \sum_{i = 1}^{n - 1}{i \over \pars{c - 1}i + n} = {1 \over c- 1}\sum_{i = 1}^{n - 1}{i \over i + n/\pars{c - 1}} \\[3mm]&= {1 \over c- 1}\sum_{i = 1}^{n - 1} \bracks{1 - {n/\pars{c - 1} \over i + n/\pars{c - 1}}} ={n - 1 \over c - 1} - {n \over \pars{c -1}^{2}}\sum_{i = 0}^{n - 2} {1 \over i + n/\pars{c - 1} + 1} \\[3mm]&= {n - 1 \over c - 1} - {n \over \pars{c - 1}^{2}} \braces{\Psi\pars{\bracks{{n \over c - 1} + 1} + n - 1} - \Psi\pars{{n \over c - 1} + 1}} \end{align} \begin{align} \color{#0000ff}{\large{\rm S}\pars{n, c \not= 1}} &= \sum_{i = 1}^{n - 1}{i \over ci + \pars{n-i}} \\[3mm]&=\color{#0000ff}{\large{n \over c - 1} + {n \over \pars{c - 1}^{2}} \bracks{\Psi\pars{{n \over c - 1}} - \Psi\pars{n\,{c \over c- 1}}}} \end{align} $\Psi\pars{z}$ is the $\it digamma$ function and we used the identities: $$ \Psi\pars{x + m} = \Psi\pars{x} + \sum_{k = 0}^{m - 1}{1 \over x + k}\,,\qquad \Psi\pars{1 + z} = \Psi\pars{z} + {1 \over z} $$

When $0 < c < 1$, the digamma functions arguments go to $-\infty$. It's convenient to use the $\it\mbox{digamma reflexion formula}$: $$ \Psi\pars{z} = \Psi\pars{1 - z} - \pi\cot\pars{\pi z} $$ $$\left\lbrace% \begin{array}{rcl} \Psi\pars{n \over c - 1} & = & \Psi\pars{1 + {n \over 1 - c}} + \pi\cot\pars{\pi n \over 1 - c} = \Psi\pars{n \over 1 - c} + {1 - c \over n} + \pi\cot\pars{\pi n \over 1 - c} \\[1mm] \Psi\pars{nc \over c - 1} & = & \Psi\pars{1 + {nc \over 1 - c}} + \pi\cot\pars{\pi nc \over 1 - c} = \Psi\pars{nc \over 1 - c} + {1 - c \over nc} + \pi\cot\pars{\pi nc \over 1 - c} \end{array}\right. $$ and \begin{align} {\rm S}\pars{n,c} &= -\,{1 \over c\pars{1 - c}} \\[3mm]&+ {n \over \pars{c - 1}^{2}}\bracks{% \Psi\pars{n \over 1 -c} - \Psi\pars{nc \over 1 - c} + \pi\cot\pars{\pi n \over 1 -c} - \pi\cot\pars{\pi nc \over 1 -c}} \\[3mm] \left.\vphantom{\LARGE A}{\rm S}\pars{n,c}\right\vert_{0\ <\ c\ < 1 \atop n\ \gg\ 1} &\sim -\,{1 \over c\pars{1 - c}} + {n \over \pars{c - 1}^{2}}\bracks{% \ln\pars{1 \over c} + \pi\cot\pars{\pi n \over 1 -c} - \pi\cot\pars{\pi nc \over 1 -c}} \end{align} where we used the digamma function $\it\mbox{asymptotic behavior}$: $\Psi\pars{z} \sim \ln\pars{z}$ when $\verts{z} \gg 1$. Notice that the $\cot$'s terms are "oscillating ones".

Notice that $$ \pi\cot\pars{\pi n \over 1 -c} - \pi\cot\pars{\pi nc \over 1 -c} = -\,{\pi\sin\pars{n\pi} \over \sin\pars{\pi n/\bracks{1 -c}}\sin\pars{\pi nc/\bracks{1 -c}}} $$ and it vanishes out whenever $n/\pars{1 - c}\ \mbox{and}\ nc/\pars{1 - c}\ \not\in {\mathbb N}$.

$\endgroup$
  • $\begingroup$ I think there is an error in the rearrangement $${1 \over c- 1}\sum_{i = 1}^{n - 1} \bracks{1 - {n/\pars{c - 1} \over i + n/\pars{c - 1}}} ={n - 1 \over c - 1} - {n \over \pars{c -1}^{2}}\sum_{i = 0}^{n - 2} {1 \over i + n\pars{c - 1} + 1}$$ $\endgroup$ – Antonio Vargas Dec 4 '13 at 5:42
  • $\begingroup$ @AntonioVargas I just checked the typo. Thanks. $\endgroup$ – Felix Marin Dec 4 '13 at 6:59
  • $\begingroup$ I'm interested to learn more about this technique, and I'm a little confused. When $c = 2/3$, say, what is $\Psi\pars{{n \over c - 1}} - \Psi\pars{n\,{c \over c- 1}}$ when $n=1$? $\endgroup$ – Antonio Vargas Dec 4 '13 at 14:14
-1
$\begingroup$
  1. There is a closed form, thanks to mathematica (using digammas):

$\frac{c n+n \psi ^{(0)}\left(\frac{c}{c-1}+\frac{n}{c-1}-\frac{1}{c-1}\right)-n \psi ^{(0)}\left(\frac{n c}{c-1}+\frac{c}{c-1}-\frac{1}{c-1}\right)-n}{(c-1)^2}$

  1. There are, therefore, asymptotics (also thanks to mathematica), on which MathJax seems to choke, here is a link to the screen grab: https://www.evernote.com/shard/s24/sh/e1d1abb1-b8a4-4f4f-bad8-7e476f73f017/7700044225f8b6d0d008346a44a2fc5d

These can be simplified, if one knew the sign of $c,$ but I leave this to you.

$\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.