- Thread starter
- #1

- Thread starter jacks
- Start date

- Thread starter
- #1

- Thread starter
- #2

= \sum_{k=0}^n \frac{1}{2^k} [z^n] (1+z)^{n+k}

= [z^n] (1+z)^n \sum_{k=0}^n \frac{1}{2^k} (1+z)^k

\\ = [z^n] (1+z)^n

\frac{1-(1+z)^{n+1}/2^{n+1}}{1-(1+z)/2}

= [z^n] (1+z)^n

\frac{2-(1+z)^{n+1}/2^{n}}{1-z}

\\ = 2\times 2^n

- [z^n] (1+z)^{2n+1} \frac{1}{2^n} \frac{1}{1-z}

\\ = 2\times 2^n

- \frac{1}{2^n} \sum_{k=0}^n {2n+1\choose k}

= 2\times 2^n - \frac{1}{2^n} \frac{1}{2} 2^{2n+1}

= 2^n.$$