Split ${n\over2}\sum_{j\ge 1}2^{-j}(1-2^{-j})^{n-1}$ into oscillating terms. Exercise 8.57 from Analysis of Algorithms (Sedgewick/Flajolet) asks for solving $p_n=2^{-n}\sum_k{n\choose k}p_k$ up to the oscillating term, for $p_0=0$ and $p_1=1$. I was able to find a functional equation for the generating function: $$P(z)=e^{z/2}P\left({z\over2}\right)+{z\over2}$$ After a long derivation, I found this formula (valid for $n\ge 2$): $$p_n={n\over2}\sum_{j\ge1}2^{-j}(1-2^{-j})^{n-1}$$ I checked small values and the formula seems to be correct. Now I want to split this into two terms, one non-oscillating and one oscillating (another example from the book has an oscillating part which is a function of the fractional part of $\log_2 n$). By bounding with an integral, I know that the non-oscillating part converges to $(2\ln 2)^{-1}\sim0.72$. But how can I extract the oscillating part from it?

I was able to solve it by using this property of integrals:

$$\int_1^\infty f(x)dx=\sum_1^\infty\int_x^{x+1}f(k)dk$$

Applying it to the sum, I get:

$$p_n={1-2^{-n}\over2\log2}+g(\\{\lg n\\})$$

Where $g(\\{\lg n\\})$ is a non-constant function of the fractional part of $\lg n$, and therefore $g(2n)=g(n)$, so it is oscillating.

The full write-up is here:

Check solution for exercise 8.57