Proof by Induction Question - as part of Russo Dye Theorem

Question

I began with $x_{n+1} = \displaystyle \frac{x+x_n}{2}$ and did the first few iterations to find that it follows this pattern: $\displaystyle \frac{(2^n-1)x+x_0}{2^n}$.

How can i show this is true for all n?

Thanks very much!

Answer 1

Hint: $$x_{n+1}=\frac{(2^n-1)x+x_0}{2^n}$$ $$x_{n+2}=\frac{x+x_{n+1}}{2}=\frac{x+\frac{(2^n-1)x+x_0}{2^n}}{2}=\frac{2^nx+(2^n-1)x+x_0}{2^{n+1}}=\frac{2^nx+2^nx-x+x_0}{2^{n+1}}$$ $$x_{n+2}=\frac{2(2^nx)-x+x_0}{2^{n+1}}=\frac{2^{n+1}x-x+x_0}{2^{n+1}}=\frac{(2^{n+1}-1)x+x_0}{2^{n+1}}$$

Then by using...