<s>[INST] How to prove that $2^{n-1}=1+1+2+4+\dotsb+2^{n-2}$ for $n>1$? This is a claim in a textbook that I'm using, although it was not proven.
When trying this for small $n$'s it is clear.
\begin{align}
2^2&=1+1+2^1=4\\
2^3&=1+1+2+2^2\\
2^4&=1+1+2+4+2^3
\end{align}
What I was thinking for the proof was $2^{n-1}=2(2^{n-2})=2^{n-2}+2^{n-2}$, but obviously that's not incorporating addition, so I don't know where to go on. Is it just expressing $2^{n-2}$ as the first summation?
 [/INST] Let $$x = \sum_{m=2}^{n}2^{m-2},$$ and note that $$1 + x = 1 + 1 + 2 + 4 + \dotsb + 2^{n-3} + 2^{n-2}\tag{1}.$$  Then, multiplying $(1)$ by $2$, we have $$2+2x = 2 + 2 + 4 + \dotsb + 2^{n-2} + 2^{n-1}\tag{2}.$$  We can rewrite $(1)$ as $$1 + x = 2 + 2 + 4 + \dotsb + 2^{n-3} + 2^{n-2}\tag{3}.$$  Subtracting $(3)$ from $(2)$ gives us $$1 + x = 2^{n-1},$$ which is the same as $$2^{n-1} = 1 + 1 + 2 + 4 + \dotsb + 2^{n-2}.$$
</s>