# Regression tree

Self-study question

Given $$(y_i, x_i)$$, $$i = 1, . . . , n$$, where $$y_i \in \mathbb{R}$$ and $$x_i ∈ R ⊂ \mathbb{R}^p$$.

Show that $$\displaystyle \sum_{i:x_i \in R_1}(y_i − \hat{y}_{R_{1}})^2 +\sum _{i:x_i \in R_2}(y_i − \hat{y}_{R_{2}})^2 \leq \sum_{i:x_{i} \in R}(y_i − \hat{y}_{R})^2$$

where $$\hat{y}_{R_{j}}$$ is the mean response for the training observations within the $$j$$th region, and $$R = R_1 \cup R_2, R_{1} \cap R_{2} = \{ \}$$. Also,

$$\hat y_{R_1}=\frac{1}{n_1}\sum_{i:x_i\in R_1} y_i,$$ $$\hat y_{R_2}=\frac{1}{n_2}\sum_{i: x_i\in R_2} y_i,$$

where $$n_{1}$$ and $$n_{2}$$ are number of observations in $$R_{1}$$, and $$R_{2}$$, respectively.

My approach:

So, I solved it in a very long way, but I was hopping that someone will propose a much simpler solution (Note: I skipped several steps between the first and the second line)

\begin{align*} \sum_{i=1}^n (y_i - \bar{y})^2 &= \sum_{i=1}^n y_i^2 - n \, \bar{y}^2 \\ &= \sum_{i=1}^{n_{1}} (y_i -\bar{y}_{1})^{2}+\sum_{i=n_{1}+1}^{n} (y_{i} - \bar{y}_{2})^{2}+ \frac{n_{1} \, n_{2}}{n} \, (\bar{y}_{1}-\bar{y}_{2})^{2}\\ & \geq \sum_{i=1}^{n_{1}}(y_i -\bar{y}_{1})^{2}+\sum_{i=n_{1}+1}^{n} (y_{i} - \bar{y}_{2})^{2} \end{align*}

$$\sum_{i=1}^n (y_i-\bar y)^2=\sum_{i=1}^{n_1} (y_i-\bar y+\bar y_1-\bar y_1)^2+\sum_{i=n_1+1}^{n} (y_i-\bar y+\bar y_2-\bar y_2)^2$$
$$\sum_{i=1}^{n_1} (y_i-\bar y+\bar y_1-\bar y_1)^2=\sum_{i=1}^{n_1} (y_i-\bar y_1)^2+\sum_{i=1}^{n_1} (\bar y_1-\bar y)^2$$ and the same for the second region, to get
$$\sum_{i=1}^n (y_i-\bar y)^2=\sum_{i=1}^{n_1} (y_i-\bar y_1)^2+\sum_{i=1}^{n_1} (\bar y_1-\bar y)^2+\sum_{i=n_1+1}^{n} (y_i-\bar y_2)^2+\sum_{i=n_1+1}^{n} (\bar y_2-\bar y)^2$$ which is the thing you want plus two non-negative things.
If you don't think it's clear that $$y_i-\bar y_1$$ and $$y_1-\bar y$$ are uncorrelated (so that my second equality doesn't need a crossproduct term) there will be an additional step in the middle to show that