Cuántas expresiones diferentes, se puede obtener mediante la inserción de paréntesis en: $x_{1}-x_{2}-\cdots-x_{n}$?

Question

Me encontré con esta pregunta y me estoy encontrando muy difícil de resolver:

Cuántas expresiones diferentes, se puede obtener mediante la inserción de paréntesis en: $$x_{1}-x_{2}-\cdots-x_{n}\quad ?$$

Por ejemplo:

$$\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*}$$

Estoy realmente desesperada por una respuesta completa. He estado trabajando en esto durante 3 horas. Gracias de antemano.

Answer 1

La respuesta es $2^{n-2}$. $x_1$ debe ser siempre positiva y $x_2$ debe ser siempre negativo. A continuación, puede elegir los signos en todo el resto de cualquier manera que usted desee, comenzando con $x_3$. Para una cadena de longitud $n$, comenzar con una cadena de longitud $n-1$ que tiene los signos de la manera que usted desea hasta allí. Si desea que la señal antes de $x_n$ a ser negativo, lo deje fuera de los paréntesis. Si quieres que sea positivo, se debe agregar a la última conjunto de paréntesis si $x_{n-1}$ está dentro de uno, o un grupo con $x_{n-1}$ si no. Steven Stadnicki el ejemplo de $x_1-x_2+x_3+x_4=x_1-(x_2-x_3-x_4)$

Answer 2

SUGERENCIA: No importa cómo usted parenthesize la expresión, al borrar los paréntesis, los dos primeros términos se $x_1-x_2$. Demostrar por inducción que el resto de los $n-2$ signos pueden ser cualquier combinación de los signos más y menos, lo que significa que para $n\ge 2$ obtener $2^{n-2}$ expresiones distintas.