1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $f$ is not a function of $n$, or is it? $\endgroup$ – Math-fun Feb 22 '16 at 11:59
  • $\begingroup$ It is ... $n$ appears both as a free and a bounded variable ... not a very good idea. Besides this: As the harmonic series does not converge ... $f \equiv \infty$. $\endgroup$ – martini Feb 22 '16 at 12:00
  • $\begingroup$ To my understanding $f$ is a function of n, otherwise this problem would not work. But I may be confused. $\endgroup$ – jake mckenzie Feb 22 '16 at 12:00
  • $\begingroup$ Part of my reason of asking this martini is that I wanted to explore this: I know the harmonic series diverge, but if I differentiate it to infinity, does that series converge? $\endgroup$ – jake mckenzie Feb 22 '16 at 12:04
  • $\begingroup$ I made some edits. I don't know if that fixes the problem. $\endgroup$ – jake mckenzie Feb 22 '16 at 12:06
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't know if this is exactly what I was looking at doing but I will read the link and report back if it was. Thank you for sharing the link. I will read it all. $\endgroup$ – jake mckenzie Feb 22 '16 at 14:24
  • $\begingroup$ Thanks, I read over the resource and I feel like it does accurately help me out. $\endgroup$ – jake mckenzie Feb 24 '16 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.