How is Welford's Algorithm derived? I am having some trouble understanding how part of this formula is derived.
Taken from:
http://jonisalonen.com/2013/deriving-welfords-method-for-computing-variance/
$(x_N−\bar{x}_N)^2+\sum_{i=1}^{N−1}(x_i−\bar{x}_N+x_i−\bar{x}_{N−1})(\bar{x}_{N−1}–\bar{x}_N)$
$=(x_N−\bar{x}_N)^2+(\bar{x}_N–x_N)(\bar{x}_{N−1}–\bar{x}_N)$
I can't seem to derive the right side from the left.
Any help explaining this would be greatly appreciated! Thanks.
 A: The key to understanding is the following algebraic identity:
$$\sum_{i=1}^{N} (x_i − \bar{x}_N) = 0$$
which basically says that the algebraic sum of deviations from the mean is zero. It is quite straightforward to derive this from the definition of mean:
$$ \bar{x}_N = \frac{1}{N} \sum_{i=1}^{N} x_i$$
This can be rewritten as:
$$ N \bar{x}_N = \sum_{i=1}^{N} x_i$$
Since mean ($\bar{x}_N $) is a constant you can rewrite multiplying it by $N$ as adding it $N$ times:
$$ \implies \sum_{i=1}^{N} \bar{x}_N = \sum_{i=1}^{N} x_i $$
Which reduces to: 
$$\sum_{i=1}^{N} (x_i − \bar{x}_N) = 0$$

Now let us look at the summation on the LHS
$$\sum_{i=1}^{N−1}(x_i−\bar{x}_N + x_i−\bar{x}_{N−1})
= \sum_{i=1}^{N−1}((x_i−\bar{x}_N) + (x_i−\bar{x}_{N−1})) \\
= \sum_{i=1}^{N−1}(x_i−\bar{x}_N) +\sum_{i=1}^{N−1} (x_i−\bar{x}_{N−1})$$
Now apply the identity stated in the beginning to the above equation, the second term vanishes on the RHS.
$$\sum_{i=1}^{N−1}(x_i−\bar{x}_N) +\sum_{i=1}^{N−1} (x_i−\bar{x}_{N−1})
= \sum_{i=1}^{N−1}(x_i−\bar{x}_N) +  0 $$
We just need a little more algebraic manipulation for the first term on the RHS.
We need the index $i$ to go from $1$ to $N$.
\begin{align}
\sum_{i=1}^{N−1}(x_i−\bar{x}_N) 
&= \left(\sum_{i=1}^{N-1}(x_i−\bar{x}_N) \right) + (x_N −\bar{x}_N) - (x_N −\bar{x}_N) \\
&= \left(\sum_{i=1}^{N-1}(x_i−\bar{x}_N)  + (x_N −\bar{x}_N) \right) - (x_N −\bar{x}_N) \\
&=  \left(\sum_{i=1}^{N}(x_i−\bar{x}_N) \right) - (x_N −\bar{x}_N)
\end{align}
The first term on the LHS vanishes leading to:
$$\sum_{i=1}^{N−1}(x_i−\bar{x}_N) = (\bar{x}_N − x_N) $$

We have now derived 
$$\sum_{i=1}^{N−1}(x_i−\bar{x}_N + x_i−\bar{x}_{N−1}) = (\bar{x}_N − x_N) $$
and plug this into the following equation:
\begin{align}
(x_N−\bar{x}_N)^2 + \sum_{i=1}^{N−1}(x_i−\bar{x}_N+x_i−\bar{x}_{N−1})(\bar{x}_{N−1}–\bar{x}_N)  
&= (x_N−\bar{x}_N)^2 + (\bar{x}_{N−1}–\bar{x}_N) \sum_{i=1}^{N−1}(x_i−\bar{x}_N+x_i−\bar{x}_{N−1}) \\
&= (x_N−\bar{x}_N)^2 + (\bar{x}_{N−1}–\bar{x}_N) (\bar{x}_N − x_N) 
\end{align}
which completes the derivation. 

One can simplify this expression further:
\begin{align}
(x_N−\bar{x}_N)^2 + (\bar{x}_{N−1}–\bar{x}_N) (\bar{x}_N − x_N) 
&= (x_N−\bar{x}_N) \left [ (x_N−\bar{x}_N) - (\bar{x}_{N−1}–\bar{x}_N) \right ] \\
&= (x_N−\bar{x}_N) (x_N − \bar{x}_{N−1})
\end{align}
A: I think the key is understanding:

and also:

The above reduces to:

This is a good post: https://alessior.wordpress.com/2017/10/09/onlinerecursive-variance-calculation-welfords-method/
