Regression Tree Impurity It seems pretty obvious that if I currently have a tree with a certain total impurity, then by splitting it again optimally, I can never end up with a greater total impurity. It seems similar to the idea of R squared.
I was wondering if there was a simple proof for this.
 A: 'optimally' is not necessary. What you really need to prove is that, impurity wouldn't increase no matter how you split. This could be done via a simple trick using concave function.
Since you didn't specify the impurity function, I'll try to be more general. In a $k$ class problem, let the impurity measure be 
$$ L(\mathbf{p})=\sum_i^k{l(p_i)}$$
where $p_i$ is the proportion of points from class $i$, and $l(\cdot)$ is concave.
Suppose in a parent node there are $(a_1,a_2,\ldots, a_k)$ samples for each class, and $(b_1,\ldots,b_k), (c_1,\ldots,c_k)$ for left child and right child separately.
Let $A=\sum_i{a_i}$, and $B,C$ are similarly defined. (thus $A=B+C $)
Then total impurity for child nodes is:
$$ \frac{B}{A}\sum_i{l(\frac{b_i}{B})}+\frac{C}{A}\sum_i{l(\frac{c_i}{C})} =
\sum_i{ \big(  \frac{B}{A} l(\frac{b_i}{B}) +\frac{C}{A}l(\frac{c_i}{C}) \big) }\\
(\mbox{Jensen's inequality}) \qquad \leq \sum_i{ l(\frac{B b_i}{AB}+\frac{Cc_i}{AC})}\\
=\sum_i{l(\frac{a_i}{A})}$$
The last row is exactly the impurity of parent node.

Now for regression impurity:
Let $y_i,i=1 \ldots n$ be the samples in parent node. Then the impurity is SSE of the following regression(with only intercept):
           $$y_i=b_0+\epsilon_i$$
Create variable $x_i=1_{(\mbox{sample } i \ \mbox{goes to left node})}$, then the impurity sum for child nodes is the SSE of regression:
$$ y_i=b_0+b_1x_i+\epsilon_i $$
SSE never increases when you add more covariates.
A: Lii's answer applies to current terminal nodes. It might be worth noting that this is true if you condition on the current configuration of the splits (in the tree above where you are proposing any split). However, if you change any split rule in the interior of the tree (not a split rule that results in 2 terminal nodes) then this isn't necessarily true. This is a result of the NP-hardness of finding an optimal tree. The tree growing process makes greedy choices at each split which may be locally optimal but aren't necessarily globally optimal. 
