Exponentially weighted average, sum of weights I'm just wondering how to actually prove that the weights of an exponentially weighted average sum to 1, like
$(1-\alpha)^n + \displaystyle\sum_{i=1}^n \alpha (1-\alpha)^{n-i} = 1$
where $\alpha \in (0, 1]$
This is mentioned in Reinforcement Learning, Barto & Sutton, first sentence of p33. Intuitively it holds true but I'd like to understand the proof of it.
 A: Just use the binomial theorem to calculate the coefficient of $\alpha^t$:
The coefficient of $\alpha^t$ in $\alpha(1-\alpha)^{n-i}$ is equal to (clearly for $n-i\geqslant t-1$ and $t>0$) the coefficient of $\alpha^{t-1}$ in $(1-\alpha)^{n-i}$ which is equal to:
$$(-1)^{t-1}\cdot\binom{n-i}{t-1}$$
So the coefficient of $\alpha^t$ in the whole thing is equal to:
$$(-1)^t\cdot\binom{n}{t}+(-1)^{t-1}\cdot\binom{n-1}{t-1}+(-1)^{t-1}\cdot\binom{n-2}{t-1}+\dotsb$$
$$=(-1)^t\Bigg(\binom{n}{t}-\binom{n-1}{t-1}-\binom{n-2}{t-1}+\dotsb\Bigg)$$
$$=(-1)^t\Bigg(\binom{n}{t}-\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}\Bigg)$$
Now one can prove that $\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}=\binom{n}{t}$ like the following:
Assume that we have $n$ people $p_1,p_2,\dotsb,p_n$ and their heights are $h_1<h_2<\dotsb<h_n$ and we put them in a row as the $i$-th person is $p_i$ and we want to choose $t$ people out of them. Casework on the tallest person we have chosen:
Since we're taking $t$ people, the tallest guy cannot be shorter that $h_t$. On the other hand if the tallest guy is to be $p_i$, the number of all ways to choose $t$ people so that the tallest one is $p_i$ is equal to $\binom{i-1}{t-1}$. So the number of all methods to choose $t$ people is $\displaystyle\sum_{\small{i=t-1}}^{n-1}\binom{i}{t-1}=\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}$. On the other hand the number of ways to choose $t$ people out of $n$ people is clearly $\binom{n}{t}$ so finally $\displaystyle\sum_{i=1}^{\small{n-t+1}}\binom{n-i}{t-1}=\binom{n}{t}$.
Back to our problem, since we proved this identity, the coefficient of $\alpha^t$ in the whole expression ($\forall t\not=0$) is equal to zero. Hence it only has constant terms and we only have one constant term in the expression (which is in the $(1-\alpha)^n$ and it is equal to $1$. So the value of $(1-\alpha)^n + \displaystyle\sum_{i=1}^n \alpha (1-\alpha)^{n-i}$ is equal to $1$.
A: First of all you can put $\alpha$ and $(1-\alpha)^n$ in front of the sigma sign:
$$(1-\alpha)^n + (1-\alpha)^{n}\cdot \alpha\sum_{i=1}^n  (1-\alpha)^{-i} $$
Factoring out $(1+\alpha)^n$
$$(1-\alpha)^n \left(1+\alpha\sum_{i=1}^n  (1-\alpha)^{-i}\right) $$
That means, that the brackets must be $(1-\alpha)^{-n}$, since $(1-\alpha)^n\cdot (1-\alpha)^{-n}=1 \quad (\color{red}*)$
The sum is the partial sum of a $\color{grey}{\textrm{geometric series}}$, where $\sum\limits_{i=1}^n x^i=x\cdot \frac{x^n-1}{x-1}$. Thus
$$1+\alpha\sum_{i=1}^n  \left(\frac1{1-\alpha}\right)^{i}=1+\frac{\alpha}{1-\alpha}\frac{\left(\frac1{1-\alpha}\right)^{n}-1}{\frac1{1-\alpha}-1}$$
$(1-a)\cdot \left( \frac1{1-\alpha}-1\right)=1-1+a=a$. Therefore the denominator is $\alpha$.
$$1+\alpha\frac{\left(\frac1{1-\alpha}\right)^{n}-1}{\alpha}=1+\left(\frac1{1-\alpha}\right)^{n}-1=\left(\frac1{1-\alpha}\right)^{n}=(1-\alpha)^{-n}$$
This is was we wanted at $(\color{red}*)$
