Consider the basic arithmetical operations of addition, subtraction, multiplication and division.
Can the sum H_n = 1+1/2+1/3+..+1/n be expressed in number of these basic operations that does not depend on n ? Supposedly this can not be done but what is the proof ?
For example the sum:
S_n = 1+2+3+...+n with n-1 additions can be expressed compactly by Gauss formula as n*(n+1)/2 where the number of operations is three and (so it does not depend on n).
I need a similar thing for H_n, or a proof that this can not be done.
Well, what Edward Smart said is quite true: Harmonic numbers are well approximated by the integral from 1 to n of 1/x, which is the natural logarithm, and in fact, Harmonic numbers (under a couple of assumptions) ARE the discrete representation of the natural logarithm. This means that you can have a generating function, but this will use logarithms. (check out: http://en.wikipedia.org/wiki/Harmonic_number, and while you are at it, you may review the description of natural logarithm and logarithm). Actually, analytic representations of discrete functions involving the natural numbers are quite related with Zeta functions. Have a look at H. M. Edwards' book: http://www.amazon.com/Riemanns-Zeta-Function-Harold-Edwards/dp/0486417409
The question is not sufficiently precise: What are the possible inputs of your computation? If anything can be the input, then one can compute H_n with no operations from H_n. If only n is allowed as input (which your example suggests), then the answer is no, because H_n is no rational function in n. This is clear by Edward Smart's remark, since H_n grows logarithmically, and no rational function does.
To Konrad Burnik, whatever the answer to your question, what is the need that you have of it? what was your original motivation, that you must use (or prove impossibility) of the usage of basic arithmetic operations for that telescopic sum? Perhaps that way we could look for another path of answering.
One can try truncated integral. Divergence of the series is known so use alternative technique of truncated integral.
Thank you all for your answers, but unfortunately I don't see any proofs for what I asked.
My impression is that most of you didn't read the question, but answered by what first came to mind.
The closest thing to a proof that this can not be done in constant operations would be the failure of Gosper's algorithm on input H_n. What I ask is a more elementary type of proof.
Thank you Michael, and of course Peter for first posting this idea.
I think this is the answer I am looking for, even though I would like to see this part in full detail:
"...a rational function has the wrong growth behaviour for large n, because H_n growths logarithmically in n"
I wanted to answer a different question (i.e. what is the greatest discovery in mathematics in the 20th century) but accidentally posted my response in the wrong forum.
The number H_n = 1+1/2+1/3+..+1/n is a rational number. What is your question Konrad. Do you want to calculate H_n in lowest terms with finite number of operations or just any representations of H_n
we know that Hn = 1+1/2+1/3+1/4+-------------1/n is divergent series when n tends to infinity.
so we can not find the sum of any natural number n, but we can write the sum of finite number as ,Sn =(n!+n!/2+n!/3+---------------n!/n)/n!
- Badges
- Science topic
- Similar topics
- Mathematics