0

I am looking to find the partial sum of the following sum for an algorithm I am analyzing: $\sum^{n-1}_{i=0} \frac{n-i-1}{n-i}$.

I can see it can be simplified to: $\sum^{n-1}_{i=0} \frac{n-i-1}{n-i}$ $= \sum^{n-1}_{i=0} (\frac{n-i}{n-i}-\frac{1}{n-i})$ $= \sum^{n-1}_{i=0} (1-\frac{1}{n-i})$

But the $\frac{1}{n-i}$ looks like the harmonic series to me. Which doesn't have a closed form. Have I done my analysis of the summation right or am I missing something?

yosmo78
  • 187

1 Answers1

1

You are correct. We have:

$$\sum_{i=0}^{n-1}\frac{n-i-1}{n-i}$$

$$\sum_{i=0}^{n-1}(1-\frac{1}{n-i})$$

$$n - \sum_{i=0}^{n-1}\frac{1}{n-i}$$

$$n-\sum_{k=1}^{n}\frac{1}{k}$$

Here, we make the substitution $k = n-i$. Thus:

$$\sum_{i=0}^{n-1}\frac{n-i-1}{n-i} = \boxed{n-H_{n}}\approx n - \ln(n) - \gamma$$

The last approximation is $H_{n}\approx \ln(n) + \gamma$, where the Euler-Mascheroni Constant $\gamma \approx 0.577$. This approximation is very good for larger values of $n$.

Joshua Wang
  • 6,103