Se S é um conjunto fechado com relação a uma operação associativa, demonstrar que se colocarmos quantos parênteses quisermos em a_{1} a_{2} \ldots a_{n}, mantendo a ordem dos elementos, obteremos o mesmo elemento em S (por exemplo, \left(a_{1} \cdot a_{2}\right) \cdot\left(a_{3} \cdot a_{4}\right)=a_{1} \cdot\left(a_{2} \cdot\left(a_{3} \cdot a_{4}\right)\right); usar indução sôbre n ).

Passo 1

O enunciado dá as seguintes informações e pede isto:
  • Dado um conjunto S e uma operação binária (que escrevemos apenas por justaposição, por exemplo xy) tal que:
    • S é fechado para essa operação: isto é, se x,y\in S então xy\in S.
    • A operação é associativa: para quaisquer x,y,z\in S vale (xy)z = x(yz).
  • O que pedir demonstrar: para quaisquer n\ge1 e quaisquer elementos a_1,a_2,\dots,a_n\in S, qualquer maneira de inserir parênteses em a_1 a_2 \ldots a_n (mantendo a ordem dos fatores) produz o mesmo elemento de S. Em outras palavras, o valor do produto não depende da colocação dos parênteses.

Passo 2

Vou explicar termos importantes para não deixar nada vago.
  • Fechamento: significa que qualquer produto de dois elementos de S ainda está em S. Isso garante que, ao calcular um produto parcial (quando colocamos parênteses e avaliamos), o resultado continua sendo elemento de S e podemos multiplicá‑lo com os restantes.
  • Associatividade: significa que, ao ter três elementos, a forma de agrupar os dois primeiros ou os dois últimos não altera o resultado, isto é (xy)z = x(yz). Essa propriedade será a única que permite trocar parênteses localmente.
  • Uma “parentetização” de a_1\cdots a_n é uma maneira de agrupar pares sucessivos até reduzir tudo a um único produto binário (equivalente a uma árvore binária completa com as folhas a_1,\dots,a_n). Por exemplo, para n=4 temos possíveis parentetizações como \big((a_1 a_2)(a_3 a_4)\big) ou \big(a_1(a_2(a_3 a_4))\big), etc.

Passo 3

Estratégia do prova: usarei indução forte sobre n.
  • Para cada n\ge1 defino a propriedade P(n): “para quaisquer a_1,\dots,a_n\in S, todo modo de inserir parênteses em a_1\cdots a_n (mantendo a ordem) dá o mesmo resultado”.
  • Vou provar P(1),P(2) (casos base) e depois mostrar que P(m) para todo m<n implica P(n).

Passo 4

Casos base.
  • n=1: há apenas um ‘produto’ possível, que é a_1 sozinho, logo P(1) é trivialmente verdadeira.
  • n=2: há apenas um modo de multiplicar a_1a_2 (não há parênteses diferentes a considerar), então P(2) também é verdadeira.

Passo 5

Caso n=3 (ilustrativo e simples uso da associatividade).
  • Há duas parentetizações não-triviais: (a_1 a_2) a_3 e a_1 (a_2 a_3).
  • Pela hipótese de associatividade, (a_1 a_2) a_3 = a_1 (a_2 a_3).
  • Assim P(3) é verdadeira. Isso mostra como a associatividade elimina a ambiguidade para três fatores.

Passo 6

Hipótese de indução forte.
  • Suponha que para todo m com 1\le m < n a propriedade P(m) é verdadeira: isto é, para qualquer sequência de m elementos de S toda parentetização dá o mesmo resultado.
  • Vamos provar P(n).

Passo 7

Tomemos uma parentetização arbitrária P de a_1 a_2 \ldots a_n.
  • Qualquer parentetização completa de n fatores pode ser vista como o produto binário de duas sub‑parentetizações: existe um k com 1\le k\le n-1 tal que P = \big(P_{\text{esq}}\big)\,\big(P_{\text{dir}}\big),onde P_{\text{esq}} é uma parentetização dos fatores a_1,\dots,a_k e P_{\text{dir}} é uma parentetização dos fatores a_{k+1},\dots,a_n.
  • Observação: essa decomposição é apenas a leitura natural de uma árvore binária: a raiz corresponde à última multiplicação feita, e os dois ramos são parentetizações de prefixo e sufixo.

Passo 8

Aplicando a hipótese de indução às sub‑parentetizações.
  • Como k<n e n-k<n, pela hipótese de indução as sub‑parentetizações têm resultados únicos. Ou seja, o valor de P_{\text{esq}} é o mesmo que o valor da parentetização “esquerda canônica” dos primeiros k fatores; denote esse valor por L_k = \text{valor de }\big((\cdots((a_1 a_2)a_3)\cdots )a_k\big),isto é, o produto dos primeiros k fatores com parênteses todos à esquerda (left-associated).
  • De modo análogo, o valor de P_{\text{dir}} é o mesmo que o valor L_{n-k}^{(k+1)} = \text{valor de }\big((\cdots((a_{k+1} a_{k+2})a_{k+3})\cdots )a_n\big),que é o produto, left-associated, dos fatores a_{k+1},\dots,a_n.
  • Portanto o valor de P é o elemento P = L_k \cdot L_{n-k}^{(k+1)}.(Aqui o expoente (k+1) só indica que L_{n-k}^{(k+1)} é o left-associated do sufixo começando em a_{k+1}.)

Passo 9

Mostrar que L_k \cdot L_{n-k}^{(k+1)} é igual ao left-associated total L_n.
  • Defina L_n explicitamente por recorrência: L_1 = a_1,\qquad L_j = (L_{j-1}) a_j\quad\text{para }j\ge2,de modo que L_n = (((\cdots((a_1 a_2) a_3)\cdots) a_n).
  • Quero provar que, para todo k com 1\le k\le n-1, L_n = L_k \cdot L_{n-k}^{(k+1)}.
  • Prova desse fato por indução sobre j (índice que vai de k+1 até n), construindo progressivamente a concatenação:
    • Defina para j\ge k+1 o elemento X_j := (((L_k\,a_{k+1})\,a_{k+2})\cdots a_j).Note que X_{k+1} = (L_k a_{k+1}) e X_n = (((L_k a_{k+1})\cdots a_n)).
    • Vou mostrar por indução em j que X_j = L_k \cdot L_{j-k}^{(k+1)}.Base j=k+1. Temos X_{k+1} = (L_k a_{k+1}). E L_{1}^{(k+1)} = a_{k+1}, então X_{k+1} = L_k\cdot L_{1}^{(k+1)}. OK.
      Passo indutivo. Suponha X_j = L_k\cdot L_{j-k}^{(k+1)}. Então X_{j+1} = (X_j\, a_{j+1}) = \big(L_k\cdot L_{j-k}^{(k+1)}\big) a_{j+1}.Aplicando a associatividade (que permite reescrever (uv)w = u(vw) para quaisquer u,v,w em S), obtemos X_{j+1} = L_k\big(L_{j-k}^{(k+1)} a_{j+1}\big).Mas \big(L_{j-k}^{(k+1)} a_{j+1}\big) é exatamente L_{j+1-k}^{(k+1)} (o left-associated dos fatores a_{k+1},\dots,a_{j+1}). Logo X_{j+1} = L_k\cdot L_{j+1-k}^{(k+1)},o que fecha o passo indutivo.
    • Aplicando o resultado para j=n obtemos X_n = L_k\cdot L_{n-k}^{(k+1)}.Mas X_n é exatamente L_n porque X_n é a forma left-associated iniciando por L_k seguido de a_{k+1},\dots,a_n, e isso coincide com a left-association total dos n fatores.
  • Assim demonstramos que para todo k com 1\le k\le n-1 vale L_n = L_k\cdot L_{n-k}^{(k+1)}.

Passo 10

Finalizando a indução.
  • Voltando ao passo 8, qualquer parentetização P vale P = L_k\cdot L_{n-k}^{(k+1)} para algum k.
  • Pelo passo 9 esse produto é L_n.
  • Portanto P = L_n. Como P foi uma parentetização arbitrária, toda parentetização de a_1\cdots a_n tem valor L_n.
  • Concluímos P(n): para os n fatores o resultado é independente da colocação dos parênteses.

Passo 11

Conclusão por indução forte.
  • Mostramos os casos base e que P(m) para todo m<n implica P(n). Logo por indução forte P(n) é verdadeira para todo n\ge1.
  • Em palavras: qualquer modo de inserir parênteses em a_1 a_2\cdots a_n (mantendo a ordem dos fatores) produz o mesmo elemento de S, graças à associatividade e ao fato de S ser fechado.

Resposta

Para quaisquer n\ge1 e quaisquer a_1,\dots,a_n\in S, todo modo de inserir parênteses em a_1 a_2 \ldots a_n (mantendo a ordem dos fatores) produz o mesmo elemento de S.

Exercícios relacionados