Pensieve header: Itai’s conjecture on the Thue-Morse sequence.

S[n_]:=(∑_(k=0)^((2^n)-1))(((-1))^(Plus@@IntegerDigits[k,2]))(k^n);
R[n_]:=(((-1))^n)(2^((n(n-1))/2))n!

S /@ Range[10]

R /@ Range[10]

S[15]

S[18] // Timing

S[20] // Timing

S[24] // Timing

R[24]