How was this summation subtracted?

Question

So I'm reading an analysis of an approximate counting algorithm. I understand that $Pr[X_{n-1} = i - 1]$ is the probability of $X_{n-1}$ being equal to $i - 1$. While $Pr[X_{n-1} = i]$ is the probability $X_{n-1}$ is equal to i.

However, I don't understand how equation 17 was derived from equation 16. How did the summation being subtracted end up being multiplied by 3?

Answer 1

Assuming the sum is over all integers $i$, the sums $$\sum_i{2^{i-1}Pr[X_{n-1} = i - 1]}$$ and $$\sum_i{2^{i}Pr[X_{n-1} = i ]}$$ are actually the same. The index of summation is shifted by $1$, but you end up getting all of the same values. Identifying them both with the second sum, this reduces to $4-1=3$ as the coefficient of the sum.

Answer 2

What values does $i$ take in each summation?

$$\sum_{i=1}^{\infty}2^{i-1}Pr\left[X_{n-1}=i-1\right]=\sum_{i=0}^{\infty}2^{i}Pr\left[X_{n-1}=i\right]$$

Answer 3

What you need to do is shift the indices on equation (16) over. Then you can add the probabilities together.

$$\sum_{i-1} 2^{i-1}Pr[X_{n-1} = i-1]$$

You also have to know the starting and ending values in order to shift (look at @SiongthyeGoh's answer).