How many different expressions can you get by inserting parentheses into: $x_{1}-x_{2}-\cdots-x_{n}$? I ran into this question and I am finding it very difficult to solve:

How many different expressions can you get by inserting parentheses into:
  $$x_{1}-x_{2}-\cdots-x_{n}\quad ?$$

For example:
$$\begin{align*}
x_{1}-(x_{2}-x_{3}) &= x_{1}-x_{2}+x_{3}\\
(x_{1}-x_{2})-x_{3}&=x_{1}-x_{2}-x_{3}\\
x_{1}-(x_{2}-x_{3})-x_{4})&=x_{1}-x_{2}+x_{3}+x_{4}\\
\end{align*}$$
I'm really desperate for a full answer. I've been working on this for 3 hours. Thanks in advance.

The answer is $2^{n-2}$.  $x_1$ must always be positive and $x_2$ must always be negative.  Then you can pick the signs on all the rest any way you want, starting with $x_3$.  For a string of length $n$, start with a string of length $n-1$ that has the signs the way you want up to there.  If you want the sign before $x_n$ to be negative, leave it outside the parentheses.  If you want it positive, add it to the last set of parentheses if $x_{n-1}$ is inside one, or group it with $x_{n-1}$ if not.  Steven Stadnicki's example of $x_1-x_2+x_3+x_4=x_1-(x_2-x_3-x_4)$
