Sum $S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$

497 Views Asked by At

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?

3

There are 3 best solutions below

0
On BEST ANSWER

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.

0
On
  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.

3
On

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