how to prove this "partial average"?

Question

I came from the programming world, i saw an exercise: "Calculate the average of a list of numbers in a functional way", then i saw an interesting answer after provide my solution.

So, lets say i have this list: $\{2, 4, 6, 8, 10\}$ I want to calculate the average, so that solution proceeded as next:

$$ \text{avg} = \frac{2 - \mathbf{0}}{1} + \frac{4 - \mathbf{2}}{2} + \frac{6 - \mathbf{3}}{3} + \frac{8 - \mathbf{4}}{4} + \frac{10 - \mathbf{5}}{5} $$

So we can say, starting from $\text{currentAverage} = 0$ and starting $\text{index} = 1 \in \{1,2,3,4,5\}$, we can calculate the average as next: $$ \sum_{i=1}^n \text{currentAverage} + \frac{(n_i - \text{currentAverage})}{\text{index}_i} $$

Where did this deduction come from? Thanks!

Answer 1

Let your list be $\{x_1, \ldots, x_n\}$. Define the average of the first $k$ numbers to be: $$ A_k = \frac{x_1 + \cdots + x_k}{k} $$ We are asked to show that: $$ A_k = A_{k-1} + \frac{x_k - A_{k-1}}{k} $$ First, let's stare at the previous average for a bit. Notice that it's easy to get the current average if those pesky denominators didn't exist. That is, it's easy to see a recurrence if we work with the total sums instead. With a little bit more work, we've derived the formula: \begin{align*} kA_k &= (k - 1)A_{k-1} + x_k \\ kA_k &= kA_{k-1} - A_{k-1} + x_k \\ A_k &= A_{k-1} + \frac{x_k - A_{k-1}}{k} \end{align*}