My question is about an analysis of an algorithm in D. E. Knuth's book The Art of Computer Programming, Vol. 1. More specifically, it is about section 1.2.10, equations 20 to 22.
First we have a generating function
$$G(z)=\frac{1}{n}z+\frac{1}{n}z^2+...\frac{1}{n}z^n=\frac{1}{n}\frac{z^{n+1}-z}{z-1}$$.
For the analysis of the algorithm $G'(1)$ and $G''(1)$ have to be calculated. These derivatives are as follows. $$G'(z)=\frac{nz^{n+1}-(n+1)z^n+1}{n(z-1)^2}$$ and $$G''(z)=\frac{n(n-1)z^{n+1}-2(n+1)(n-1)z^n+n(n+1)z^{n-1}-2}{n(z-1)^3}$$ By setting $z=1$ one realizes that $G'(1)=\frac{0}{0}=undefined$ and $G''(1)=\frac{0}{0}=undefined$. Therefore the two values needed cannot easily be determined.
To circumvent any too tedious calculations, Knuth creates a Taylor series $$G(1+z)=G(1)+G'(1)z+\frac{G''(1)}{2!}z^2+...$$ by replacing $z$ by $z+1$ in the first equation $$G(1+z)=\frac{1}{n}\frac{(1+z)^{n+1}-1-z}{z}$$.
In the last step Knuth transforms this term again to a Taylor series $$G(1+z)=1+\frac{n+1}{2}z+\frac{(n+1)(n-1)}{6}z^2+...$$ and this was the point where I had to surrender. How does one get from the second last equation to the last equation? There probably is a simple explanation, but I have been thinking about it for hours and haven't come up with any reasonable idea.
The essential tool is the binomial formula $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}$$
Expanding $(1+z)^{n+1}$ in the second last formula gives $$(1+z)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} z^k = 1 + (n+1) z + \frac{(n+1) \cdot n}{2} z^2 + \frac{(n+1) \cdot n \cdot (n-1)}{6} z^3 + \ldots$$
Hence,
$$(1+z)^{n+1} - 1- z = n\cdot z + \frac{(n+1) \cdot n}{2} z^2 + \frac{(n+1) \cdot n \cdot (n-1)}{6} z^3 + \ldots$$
Dividing by $n \cdot z$ gives the desired formula
$$\frac{(1+z)^{n+1} - 1 - z}{n \cdot z} = 1 + \frac{n+1}{2} z + \frac{(n+1)(n-1)}{6} z^2 + \ldots$$