bhuber@sjuvax.UUCP (B. Huber) (11/27/85)
For k>=0, let a(k) be 2^k / k (one over k, times the kth power of 2). Can you find the sum of a(k) as k ranges from 1 to n as a closed formula in n? I suspect not, but cannot yet find a way to show that it is impossible. The answer is of some interest. It would yield a closed formula for the sums of reciprocals of entries in Pascal's triangle (summed over individual rows). Thus it would give a formula for the resistance through a circuit shaped like an n-cube (a problem which appeared in net.physics two months ago). A nice little mathematical puzzle is to find the exact relationship between the two sums which I have mentioned. In particular, can you find it using only elementary techniques (algebraic, not transcendental; formal power series, etc., not allowed)?
ghgonnet@watdaisy.UUCP (Gaston H Gonnet) (11/30/85)
> > For k>=0, let a(k) be 2^k / k (one over k, times the kth power of 2). ===================== you probably mean k>0 ===================== > Can you find the sum of a(k) as k ranges from 1 to n as a closed formula > in n? > A "closed formula" is a fuzzy concept, it depends on your set of primitive functions. E.g. Hn = sum(1/k,k=1..n) cannot be expressed in terms of + - * and /, but it can be expressed in terms of psi(x). I do not know any "closed form" for the above, if it is of any help, it has an asymptotic expansion like: sum( 2^k/k, k=1..n) = 2^(n+1) / n * ( 1 + 1/n + 3/n^2 + 13/n^2 + 75/n^4 + O(1/n^5) ) For a more general case ( sum( z^k/k, k=1..n ) ) there is also an asymptotic formula, see the "Handbook of Algorithms and Data Structures", Addison Wesley, p. 210 (II.1.7))
leimkuhl@uiucdcsp.CS.UIUC.EDU (12/02/85)
Well the given problem can be looked at as an integration problem:
Sum{x^k/k} = Sum{ Int{ s^(k-1)} - 1/k}
k=1,n k=1,n 1<s<=x
= Int{ Sum{ s^k}} - Sum{1/k}
1<s<=x k=0,n-1 k=1,n
= Int{(s^n - 1)/(s-1)} - Sum{1/k}
1<s<=x k=1,n
Where by Int{f(s)}, we mean lim{ Int{f(s)}}. Since f is continuous
a<s<=b u->a+ u<=s<=b
and bounded in our case, this makes sense.
I let Macsyma have a crack at the integral, but it proved too tough. For this
reason, I doubt the existence of a simple closed form. There is always
the problem of determining what functions are in the space of acceptable
functions (indeed, in one sense the given sum is already in closed form,
for it has a finite number of closed terms.)
Does anyone have a good book of integrals handy?
-Ben Leimkuhlerpumphrey@ttidcb.UUCP (Larry Pumphrey) (12/03/85)
> For k>=0, let a(k) be 2^k / k (one over k, times the kth power of 2). > Can you find the sum of a(k) as k ranges from 1 to n as a closed formula > in n? > I suspect not, but cannot yet find a way to show that it is impossible. I suspect so, how about k=n 2^k (n+2) f(n) = sigma ----- = 2 - ----- k=0 k 2^n
pumphrey@ttidcb.UUCP (Larry Pumphrey) (12/03/85)
>> For k>=0, let a(k) be 2^k / k (one over k, times the kth power of 2). >> Can you find the sum of a(k) as k ranges from 1 to n as a closed formula >> in n? >> I suspect not, but cannot yet find a way to show that it is impossible. > I suspect so, how about > k=n 2^k (n+2) > f(n) = sigma ----- = 2 - ----- > k=0 k 2^n I'll print my own correction, my erroneous "solution" was broadcast before I had a chance to retract it. Obviously, I interchanged the numerator and denominator which makes the problem trivial. Sorry about that :-(
leimkuhl@uiucdcsp.CS.UIUC.EDU (12/08/85)
I think you should have checked your formula out before you post it.
The formula you've posted is for Sum{ k / 2^k } not Sum { 2^k / k}.
I do not think there is a simple closed form. The above is very
simple to derive because Sum{ kx^k } = x Sum{ kx^(k-1) }
= x derivative{ Sum{ x^k } }, which has a known simple closed form.
The case x=.5 gives us the formula. As I've pointed out in an
earlier note, the actual problem involves integrating the formula
for Sum{ x^k } (at least if we want a general formula) and this does
not seem promising. The Possibility exists that there is a simple
closed form for Sum{ 2^k / k }, but not for Sum{ x^k / k }. However,
I see no reason why 2 should have such a distinction.
-Ben Leimkuhlerbhuber@sjuvax.UUCP (B. Huber) (12/13/85)
> I think you should have checked your formula out before you post it. > > The formula you've posted is for Sum{ k / 2^k } not Sum { 2^k / k}. > > ... > -Ben Leimkuhler You are quite correct to ask me to check out my formula, or any formula for that matter, before posting it. As has been kindly pointed out by another respondent, I carelessly did not restrict k to be nonzero in the expression. I am happy that that was an unimportant mistake, easily corrected. Your reference to a 'formula', though, mystifies me. My copy of the original posting says only: >For k>=0, let a(k) be 2^k / k (one over k, times the kth power of 2). >Can you find the sum of a(k) as k ranges from 1 to n as a closed formula >in n? ... >The answer is of some interest. It would yield a closed formula for the >sums of reciprocals of entries in Pascal's triangle (summed over individual >rows). ... >A nice little mathematical puzzle is to find the exact relationship between >the two sums which I have mentioned. In particular, can you find it using >only elementary techniques (algebraic, not transcendental; formal power >series, etc., not allowed)? I can find no formula that needs 'checking'. But I'll give it here, both to show how beautiful it is, and to ask others with an algebraic bent whether you can prove it true, using only algebraic techniques. __________________________________________________________________________ |The sum of a(k), as k ranges from one to n+1, all divided by a(n+1), | |equals | |the sum of the reciprocals of the binomial coefficients C(n,k) as k ranges| |from 0 to n. | |__________________________________________________________________________| As an illustration, here are the first several sums: n=1: (2/1) / (2/1) = 1/1 n=2: (2/1 + 4/2) / (4/2) = 1/1 + 1/1 n=3: (2/1 + 4/2 + 8/3) / (8/3) = 1/1 + 1/2 + 1/1 n=4: (2/1 + 4/2 + 8/3 + 16/4) / (16/4) = 1/1 + 1/3 + 1/3 + 1/1 ... My derivation of this is rather messy, and transcendental in flavor (solving boundary value problems, e.g.). Hence the desire for a nicer proof. By the way Ben, I really would like to see what this has to do with the sum of {k / 2^k}.