# How to simply the sum $\sum\limits_{k=1}^n\frac{N-n+k}{(N-k+1)(N-k+1)(N-k)}$?

Let $N>0$ be a large integer, and $n<N$, then how to simply the following sum $$\sum\limits_{k=1}^n\frac{N-n+k}{(N-k+1)(N-k+1)(N-k)}.$$ Thank you very much, guys.

Actually for another similar sum $\sum\limits_{k=1}^n\frac{1}{(N-k+1)(N-k)}=\sum\limits_{k=1}^n\frac{1}{N-k}-\frac{1}{N-k+1}=\frac{1}{N-n}-\frac{1}{N}$, I know the trick. But adding one term of such thing, $\frac{N-n+k}{N-k+1}$, it becomes difficult.

So, thanks a million for any clue.

• Do you mean the repeated factor in the denominator? Oct 5 '16 at 3:14

I am not sure that you will like it.

$$S_n=\sum\limits_{k=1}^n\frac{N-n+k}{(N-k+1)^2(N-k)}$$ $$S_n=\frac{n (n-2 N)}{N (n-N)}+(n-2 N-1)\, \big(\psi ^{(1)}(-N)-\psi ^{(1)}(n-N)\big)$$ where appears the first derivative of the digamma function. I do not think that this could be further simplified. The trouble is that $\psi ^{(1)}(m)$ is undefined for $m\leq 0$.

May be, you could prefer the following. Considering for large values of $N$ $$\frac{N-n+k}{(N-k+1)^2(N-k)}=\left(\frac{1}{N}\right)^2+\frac{4 k-n-2}{N^3}+\frac{9 k^2-3 k n-10 k+2 n+3}{N^4}+\frac{16 k^3-6 k^2 n-28 k^2+8 k n+18 k-3 n-4}{N^5}+\frac{25 k^4-10 k^3 n-60 k^3+20 k^2 n+60 k^2-15 k n-28 k+4 n+5}{N^6}+O\left(\frac{1}{N^7}\right)$$ and now summing from $k=1$ to $k=n$, we should get, as an approximation, $$S_n=\frac{n \left(N \left(6 N^3-3 N+2\right)+1\right)}{6 N^6}+\frac{n^2 \left(6 N^3-6 N+5\right)}{6 N^6}+\frac{n^3 (N (9 N-2)-10)}{6 N^6}+\frac{n^4 (12 N-5)}{6 N^6}+\frac{5 n^5}{2 N^6}$$

For sure, we could add more terms for higher accuracy. For illustration purposes, I used $N=1000$ and varied $n$. The following table reports the decimal values of the exact sum and of the ugly approximation. $$\left( \begin{array}{ccc} n & \text{exact} & \text{approximation} \\ 50 & 0.00005270 & 0.00005270 \\ 100 & 0.00011173 & 0.00011173 \\ 150 & 0.00017880 & 0.00017876 \\ 200 & 0.00025625 & 0.00025600 \\ 250 & 0.00034721 & 0.00034618 \\ 300 & 0.00045610 & 0.00045276 \\ 350 & 0.00058916 & 0.00057993 \\ 400 & 0.00075548 & 0.00073276 \\ 450 & 0.00096866 & 0.00091727 \\ 500 & 0.00124975 & 0.00114053 \end{array} \right)$$

• this doesn't answer the question ; the title specifies "simply" and not the brute calculus ...
– user354674
Oct 5 '16 at 4:35
• @igael. There is no simple expression. The exact result is the first one I gave. Oct 5 '16 at 4:37
• if there is no simple expression, the answer is simply "no"
– user354674
Oct 5 '16 at 4:46
• og N ? is it a log ? yes, perhaps there is no trick ...
– user354674
Oct 5 '16 at 5:12
• @igael. Sorry for the typo og was supposed to be of. On French keyboards, f and g are next to eachother. Oct 5 '16 at 5:37

With the same method which you have used above you get

$$\sum\limits_{k=1}^n \frac{N-n+k}{(N-k+1)^2(N-k)}=\frac{n(2N-n)}{N(N-n)}-(2N+1-n)\sum\limits_{k=1}^n \frac{1}{( N-k+1)^2}$$

Hints:

$\enspace N-n+k=(2N+1-n)-(N-k+1)$

$\enspace \displaystyle \frac{1}{(N-k+1)^2(N-k)}=\frac{1}{N-k}-\frac{1}{N-k+1}-\frac{1}{(N-k+1)^2}$

The closed form for $\sum\limits_{k=1}^n \frac{1}{( N-k+1)^2}$ is:

$$\sum\limits_{k=1}^n \frac{1}{( N-k+1)^2}= \sum\limits_{k=1}^N \frac{1}{k^2} -\sum\limits_{k=1}^{N-n} \frac{1}{k^2}=$$$$((\frac{1}{N!} \begin{bmatrix} N+1 \\ 2 \end{bmatrix})^2-\frac{2}{N!} \begin{bmatrix} N+1 \\3 \end{bmatrix})-((\frac{1}{(N-n)!} \begin{bmatrix} N-n+1 \\ 2 \end{bmatrix})^2-\frac{2}{(N-n)!} \begin{bmatrix} N-n+1 \\3 \end{bmatrix})$$

where $\begin{bmatrix} n \\ k \end{bmatrix}$ is called unsigned Stirling number of the first kind .

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\color{#f00}{% \sum_{k = 1}^{n}{N - n + k \over \pars{N - k + 1}\pars{N - k + 1}\pars{N - k}}} \\[5mm] = &\ \pars{2N - n}\pars{\sum_{k = 1}^{n}{1 \over k - N - 1} - \sum_{k = 1}^{n}{1 \over k - N}} - \pars{2N - n + 1}\sum_{k = 1}^{n}{1 \over \pars{k - N - 1}^{2}} \\[5mm] = &\ {\pars{2N - n}n \over N\pars{N - n}} - \pars{2N - n + 1}\sum_{k = 1}^{n}{1 \over \pars{k - N - 1}^{2}} \end{align}

Note that

$$\left\{\begin{array}{rcl} \ds{\sum_{k = 1}^{n}{1 \over k + a}} & \ds{=} & \ds{\sum_{k = 0}^{n - 1}{1 \over k + 1 + a} = \sum_{k = 0}^{\infty}\pars{{1 \over k + 1 + a} - {1 \over k + n + 1 + a}} = H_{n + a} - H_{a}} \\[2mm] \ds{\sum_{k = 1}^{n}{1 \over \pars{k + a}^{2}}} & \ds{=} & \ds{\partiald{}{a}\pars{H_{a} - H_{n + a}} = \Psi\,'\pars{1 + a} - \Psi\,'\pars{1 + n + a}} \end{array}\right.$$

$\ds{H_{z}}$ is the Harmonic Number and $\ds{\Psi\,'}$ is the Trigamma Function.

Then, \begin{align} &\color{#f00}{% \sum_{k = 1}^{n}{N - n + k \over \pars{N - k + 1}\pars{N - k + 1}\pars{N - k}}} \\[5mm] = &\ \color{#f00}{{\pars{2N - n}n \over N\pars{N - n}} - \pars{2N - n + 1}\bracks{\Psi\,'\pars{-N} - \Psi\,'\pars{-N - n}}} \end{align}

Any issue with the Trigamma's argument signs can be deal with the Euler Reflection Formula or/and the Recurrence Formula:

$$\left\{\begin{array}{rcl} \ds{\Psi\,'\pars{z}} & \ds{=} & \ds{-\Psi\,'\pars{1 - z} + \pi^{2}\csc^{2}\pars{\pi z}} \\[2mm] \ds{\Psi\,'\pars{z + 1}} & \ds{=} & \ds{\Psi\,'\pars{z} - {1 \over z^{2}}} \end{array}\right.$$