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