For every $n$, $\sum\limits_{m=0}^{\infty}\left(-\frac{1}{2}\right)^m\sum\limits_{l=0}^m\left(\frac{1}{2^{n-1}}-2\right)^{m-l} {n \choose l}=1$

Question

Show that for every $n$ we have that

$$\sum_{m=0}^{\infty}\left[\left(-\frac{1}{2}\right)^m\sum_{l=0}^m\left(\left[\frac{1}{2^{n-1}}-2\right]^{(m-l)}{n \choose l} \right)\right]=1$$

Hint: Represent the function

$$F(x) =\sum_{m=0}^{\infty}\left[x^m\sum_{l=0}^m\left(\left[\frac{1}{2^{n-1}}-2\right]^{(m-l)}{n \choose l} \right)\right]$$

as the product of two generating functions.

I'm really stuck. We know that

$$1 - \frac{1}{2} + \frac{1}{4} - \frac{1}{8} +... = \frac{1}{1+\frac{1}{2}} =\frac{2}{3}$$

So I thought it would be enough to show that $\forall m$

$$\sum_{l=0}^m\left(\left[\frac{1}{2^{n-1}}-2\right]^{(m-l)} {n \choose l} \right) = \frac{3}{2}$$

But

1) I've had a hard time trying to show that the sum above has a constant value independent of $m$ (by transforming $2^{n-1}$ in a sum of binomial coefficients, and seeing if something gets cancelled out).

2) The hint confuses me. As noticed, I wasn't applying it in my only attempt, and at the same time I don't know how to take advantage of that fact.

Answer 1

Let's assume we don't know any hint. A technique which is often helpful is exchanging sums.

We obtain \begin{align*} \sum_{m=0}^\infty&\left(-\frac{1}{2}\right)^m\sum_{l=0}^m\left(\frac{1}{2^{n-1}}-2\right)^{m-l}\binom{n}{l}\\ &=\sum_{l=0}^\infty\sum_{m=l}^\infty\left(-\frac{1}{2}\right)^m\left(\frac{1}{2^{n-1}}-2\right)^{m-l}\binom{n}{l}\tag{1}\\ &=\sum_{l=0}^\infty\binom{n}{l}\sum_{m=0}^\infty\left(-\frac{1}{2}\right)^{m+l}\left(\frac{1}{2^{n-1}}-2\right)^{m}\tag{2}\\ &=\sum_{l=0}^\infty\binom{n}{l}\left(-\frac{1}{2}\right)^{l}\sum_{m=0}^\infty\left(1-\frac{1}{2^{n}}\right)^{m}\tag{3}\\ &=\left(1-\frac{1}{2}\right)^n\frac{1}{1-\left(1-\frac{1}{2^n}\right)}\tag{4}\\ &=1 \end{align*} and the claim follows.

Comment:

• In (1) we exchange the series by noting \begin{align*} \sum_{m=0}^\infty\sum_{l=0}^m a_{m,l}=\sum_{0\leq l\leq m< \infty} a_{m,l}= \sum_{l=0}^\infty\sum_{m=l}^\infty a_{m,l} \end{align*}

• In (2) we shift the index $m$ of the inner sum by $l$ to start from $m=0$ and we do a small rearrangement.

• In (3) we simplify the expression and observe the double series is in fact a product of two series.

• In (4) we apply the formula for the binomial series expansion and for the geometric series.