0
$\begingroup$

I am trying to find a tight bound on the following sum: \begin{align} \sum_{i=1}^n \sum_{k=1}^i \frac{1}{(n-k+1)^2} \end{align}

If we use Wolfram_Alpha, we can actually find a closed-form expression: \begin{align} \sum_{i=1}^n \sum_{k=1}^i \frac{1}{(n-k+1)^2}=\gamma+\psi(1-n)+\frac{1}{n} \end{align} where $\gamma$ is Euler constant and $\psi$ is the digamma function. The exact result is a bit confusing to me. Specifically, I never seen the digamma function for negative integers.

$\endgroup$

1 Answer 1

1
$\begingroup$

Hint : $$\sum_{i=1}^n \sum_{k=1}^i \frac{1}{(n-k+1)^2} = \sum_{k=1}^n \sum_{i=k}^n \frac{1}{(n-k+1)^2} = \sum_{k=1}^n \frac{n-k+1}{(n-k+1)^2} = \sum_{k=1}^n \frac{1}{n-k+1}$$

$\endgroup$
2
  • $\begingroup$ Can you explain the first step? The rest I follow $\endgroup$
    – Lisa
    Aug 28, 2020 at 16:26
  • $\begingroup$ I interverted the two summations, changing the indices : $\sum_{i=1}^n \sum_{k=1}^i a_{ik} = \sum_{k=1}^n \sum_{i=k}^n a_{ik}$. $\endgroup$ Aug 28, 2020 at 16:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .