[Math] Finite derivative of the harmonic series

derivativesdiscrete mathematicssequences-and-seriessummation

In Knuth's Concrete Mathematics he represents the famous quicksort algorithm in computer science as a infinite sum then shows that sum can be simplified to being essentially harmonic. I want to explore this sum more by taking a finite derivative of the function but I have not taken any discrete math courses and am struggling with notation.

My question:

Suppose, $$f(n)=\sum_{n=0}^\infty \frac{1}{n+1}$$

Now suppose we take the generalized finite difference of that function,
$$\Delta _h^\mu [f](x)=\sum_{x=0}^\infty \mu_k f(x+kh)$$

Have I set this up properly?

I want to explore the finite difference of this series. If I have not set this up correctly, might you point me in the right direction of what I might read to learn how to do this myself. Thank you.

Best Answer

You probably mean $$f(n)=\sum_{k=1}^n \frac{1}{k}\approx \ln n+\gamma $$ As a sum is basically a discrete integral, the finite derivative of a sum over the upper bound gives you back the summand $f'(n)\asymp \frac{1}{n}$. More formal treatment of differentiation of discrete sums is found here.

Anyway, I think you can deal with the finite difference implementation now: the difference between two partial sums for different $n$ shouldn't be a problem.

Related Question