# Error in infinite sum [duplicate]

The binary weight of the non negative integer k is defined by

w[k_] := Total[IntegerDigits[k, 2]]


The first values are (cf. http://oeis.org/ A000120)

Table[w[k], {k, 0, 10}]

(*
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2}
*)


Now define formally the generating function

g[z_] = Sum[w[k] z^k, {k, 0, ∞}]

(*
(2 - z)/(-1 + z)^2
*)


Most surprisingly, Mathematica returns an explicit result.

But this can't be correct, as the expansions about z = 0 differ

Sum[w[k] z^k, {k, 0, 5}]

(*
z + z^2 + 2 z^3 + z^4 + 2 z^5
*)

Series[(2 - z)/(-1 + z)^2, {z, 0, 5}] // Normal

(*
2 + 3 z + 4 z^2 + 5 z^3 + 6 z^4 + 7 z^5
*)


It looks as if in the infinite sum the function w[k] is replaced by (k + 2).

Any explanation? Seems to be a bug.

EDIT #1

24.02.15 19:08

To avoid the head replacement effect pointed out by belisarius we can consider the function

w1[n_] := n - Sum[IntegerExponent[k, 2], {k, 1, n}]


which is identical to w[k] for any k.

Now the infinite sum

g1[z_] = Sum[w1[n] z^n, {n, 0, \[Infinity]}]


is returned unevaluated, as it "should" (because it is too complicated)

$\sum _{n=0}^{\infty } z^n \left(n-\sum _{k=1}^n \text{IntegerExponent}[k,2]\right)$

So my discovery is not a bug, but I have learned the lesson that one should be very careful with infinite sums and their interpretation of the terms to be added.

## marked as duplicate by Mr.Wizard♦Nov 20 '16 at 19:10

• Interestingly, Mathematica requires several seconds to compute Sum[w[k] .1^k, {k, 0, 999999}], returning 0.112122. But Sum[w[k] .1^k, {k, 0, 1000000}] returns almost instantly with 2.34568. Yes, I would say that this is a bug. – bbgodfrey Feb 24 '15 at 12:14
• Finite sums are computed by addition up to 10^6-1 terms. Above that symbolic methods are used by default. Per @belisarius explanation of Total behavior, and the procedural summation cutoff of a million, no bug here. On a related note, I think some information about this may be found in the documentation. Also mentioned in a prior MSE post, though offhand I do not recall which one that was. – Daniel Lichtblau Feb 24 '15 at 16:28
• @DanielLichtblau I only remember this one – Dr. belisarius Feb 24 '15 at 17:11
• This, I believe – Daniel Lichtblau Feb 25 '15 at 0:59
• @DanielLichtblau Thanks for the link. – Dr. Wolfgang Hintze Feb 25 '15 at 14:22

The problem is that Total[] works with any head. So:

Total[Derivative[1, 2, 1]]
(* 4 *)

Total[IntegerDigits[k, 2]]
(* 2 + k *)


And so you can expect

Sum[(2 + k) z^k, {k, 0, ∞}] == Sum[Total[IntegerDigits[k, 2]] z^k, {k, 0, ∞}]