Saltar para o conteúdo
Topos Uranos
Português

Somatórios, progressões e indução

Resumo

Esta aula introduz a notação de somatório e suas propriedades (linearidade, decomposição, deslocamento do índice e inversão da ordem), e a aplica ao cálculo de somas telescópicas e das somas das progressões aritméticas e geométricas. Estuda depois a indução forte e o princípio da boa ordenação, demonstra que a indução implica ambos, precisa em que sentido são equivalentes a ela e os emprega para provar que todo natural maior que 11 é produto de primos.

Objetivos de aprendizagem

  1. Escrever e transformar somas com a notação de somatório, aplicando suas propriedades de linearidade, decomposição, deslocamento do índice e inversão da ordem.
  2. Calcular somas telescópicas e empregá-las para deduzir, e não apenas verificar, fórmulas de somas.
  3. Determinar o termo geral e a soma dos primeiros termos de uma progressão aritmética ou geométrica, e aplicá-los à resolução de problemas.
  4. Demonstrar com a indução forte e com o princípio da boa ordenação, deduzir ambos do princípio de indução e explicar com que fatos adicionais a boa ordenação permite recuperar a indução.

A notação de somatório

Na aula sobre os axiomas de Peano apareceram somas de muitos termos que seguem uma regra, como 1+2+⋯+n1 + 2 + \cdots + n. As reticências confiam ao leitor a tarefa de adivinhar essa regra; a notação de somatório a declara. Se am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n são números, com m≤nm \leq n, escreve-se

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

e lê-se “a soma de aka_k para kk desde mm até nn”. A letra kk é o índice da soma; mm e nn são seus limites inferior e superior, e aka_k é o termo geral. A soma tem n−m+1n - m + 1 termos. O índice é uma variável muda: o valor da soma não depende da letra com que é nomeado, de modo que ∑k=1nk2\sum_{k=1}^{n} k^2 e ∑j=1nj2\sum_{j=1}^{n} j^2 são o mesmo número. O índice percorre números naturais; os termos, ao contrário, podem ser números de outro tipo. Nesta aula aparecem, além de naturais, números inteiros com seus negativos e frações, que a unidade seguinte constrói: aqui são antecipados, e deles se usam apenas as regras elementares de cálculo e de ordem (comutatividade, associatividade, distributividade, as regras dos sinais, a subtração e a divisão por um número não nulo). As propriedades do somatório que seguem se demonstram com essas regras e valem, portanto, para termos de qualquer desses tipos.

Como a soma, o produto e a potência na aula sobre as operações com números naturais, o somatório admite uma definição recursiva que dispensa as reticências: a soma de um só termo é esse termo, e para acrescentar um termo soma-se ao resultado anterior.

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

Esta definição começa em mm, ao passo que o teorema da recursão, tal como foi enunciado, define funções a partir do 11. Ora, basta transladar o índice: em lugar da soma até nn define-se a soma dos qq primeiros termos a partir de ama_m. Com o valor inicial ama_m e a regra gq(x)=x+am+qg_q(x) = x + a_{m + q}, o teorema da recursão dá uma única função FF de N\mathbb{N} nos números tal que F(1)=amF(1) = a_m e F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} para todo natural qq. Para n≥mn \geq m define-se então a soma até nn como o valor de FF no número de seus termos, n−m+1n - m + 1, que é um natural porque m<n+1m < n + 1:

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

Com n=mn = m obtém-se F(1)=amF(1) = a_m, e com q=n−m+1q = n - m + 1, como m+q=n+1m + q = n + 1, a igualdade F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} é exatamente a segunda regra da definição. Donde a definição recursiva desde mm determina uma única soma para cada n≥mn \geq m, e, se m=1m = 1, coincide com a que o teorema da recursão dá diretamente, porque então F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k.

Com esta notação, a fórmula demonstrada por indução na aula sobre os axiomas de Peano, a da soma dos nn primeiros naturais, escreve-se assim:

∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}

A soma dos quadrados, ∑k=1nk2\sum_{k=1}^{n} k^2, é o passo seguinte, e esta aula não se limitará a verificá-la: a seção sobre as somas telescópicas a deduz sem conhecê-la de antemão.

As induções sobre o limite superior de uma soma começam no limite inferior mm, que não precisa ser 11. Ora, o princípio de indução dos axiomas de Peano começa em 11; para começar em outro natural, é necessário o lema seguinte.

LemaIndução a partir de um natural qualquer

Seja n0n_0 um natural. Se uma propriedade se verifica para n0n_0 e, admitido que se verifica para um natural qualquer k≥n0k \geq n_0, se verifica também para k+1k + 1, então essa propriedade se verifica para todos os naturais n≥n0n \geq n_0. A ideia é renumerar os naturais a partir de n0n_0 para voltar ao princípio de indução ordinário. Usam-se o lema da aula sobre as operações com números naturais segundo o qual todo natural distinto de 11 é um sucessor, e a monotonia da soma. Na figura, n0=4n_0 = 4 e p=3p = 3: debaixo de cada natural a partir de n0n_0 figura seu novo número qq.

Demonstração

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    Se n0=1n_0 = 1, é o princípio de indução. Se não, n0=p+1n_0 = p + 1 para algum natural pp, e consideramos a propriedade QQ que afirma PP para p+qp + q.

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    A propriedade QQ se verifica para 11, porque Q(1)Q(1) é P(n0)P(n_0).

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    Se Q(q)Q(q) se cumpre, como 1≤q1 \leq q, pela monotonia da soma tem-se p+q≥p+1=n0p + q \geq p + 1 = n_0, e o passo dado se aplica a k=p+qk = p + q: cumpre-se Q(q+1)Q(q + 1).

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    Pelo princípio de indução, Q(q)Q(q) vale para todo qq. Todo n≥n0n \geq n_0 é da forma p+qp + q: se n=n0n = n_0, com q=1q = 1, e se n=n0+ln = n_0 + l, com q=1+lq = 1 + l.

Propriedades do somatório

Da definição recursiva deduzem-se, por indução sobre o limite superior, as propriedades seguintes, válidas para termos quaisquer aka_k e bkb_k e para qualquer número cc:

  1. Linearidade: ∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k e ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k. Em particular, somar nn vezes uma constante é multiplicá-la por nn: ∑k=1nc=nc\sum_{k=1}^{n} c = nc.
  2. Decomposição: se m≤p<nm \leq p < n, então ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k.
  3. Deslocamento do índice: para todo natural pp, ∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}.
  4. Inversão da ordem: ∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}.
TeoremaPropriedades do somatório

Para termos quaisquer aka_k e bkb_k e para qualquer número cc, o somatório é linear, decompõe-se em duas somas consecutivas, admite o deslocamento do índice e a inversão da ordem, nos termos da lista anterior. Cada propriedade se demonstra por indução sobre o limite superior, que começa no inferior graças ao lema anterior. Usam-se apenas a definição recursiva e as propriedades da soma e do produto; a inversão apoia-se, além disso, na decomposição e no deslocamento.

Demonstração

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    Linearidade. Para n=mn = m, ambos os lados valem am+bma_m + b_m. Se vale para nn, aplicam-se a definição recursiva, a hipótese de indução e a associatividade e a comutatividade da soma. Do mesmo modo, com a distributividade, prova-se que ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k, e que ∑k=1nc=nc\sum_{k=1}^{n} c = nc, porque nc+c=(n+1)cnc + c = (n + 1)c.

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    Decomposição, com pp fixo, por indução sobre nn a partir de p+1p + 1. Para n=p+1n = p + 1 é a definição recursiva, porque a soma de um só termo é esse termo.

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    Se a decomposição vale para nn, acrescenta-se o termo an+1a_{n + 1} a ambos os lados e aplica-se a definição recursiva a cada soma.

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    Deslocamento. Para n=mn = m, ambos os lados valem ama_m. Se vale para nn, como o limite superior (n+p)+1(n + p) + 1 é (n+1)+p(n + 1) + p, aplicam-se a definição recursiva e a hipótese de indução.

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    Inversão, por indução sobre nn. Para n=1n = 1, ambos os lados valem a1a_1. Se vale para nn, separa-se o primeiro termo da soma invertida de n+1n + 1 termos pela decomposição, e desloca-se o índice em uma unidade, com j=i+1j = i + 1.

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    Pela hipótese de indução, a última soma vale ∑k=1nak\sum_{k=1}^{n} a_k; pela comutatividade e pela definição recursiva, obtém-se a inversão para n+1n + 1.

A linearidade permite reduzir uma soma complicada a somas conhecidas. As duas últimas propriedades são mudanças de variável: o deslocamento substitui k=j−pk = j - p e percorre os mesmos termos com outra numeração, e a inversão substitui k=n+1−jk = n + 1 - j e os percorre do último ao primeiro. Ora, o somatório não se comporta do mesmo modo com o produto: a soma dos produtos não é o produto das somas. Basta um exemplo com dois termos e ak=bk=ka_k = b_k = k:

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
ProposiçãoA soma dos primeiros ímpares

Demonstrar que a soma dos nn primeiros números ímpares é n2n^2. A linearidade reduz a soma a outras duas já conhecidas, sem necessidade de uma nova indução.

Demonstração

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    O ímpar que ocupa o lugar kk é 2k−12k - 1: o primeiro é 11, o segundo 33 e o de lugar nn é 2n−12n - 1. A soma pedida escreve-se assim.

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    Pela linearidade, a soma separa-se em duas: o dobro da soma dos kk, menos a soma de nn uns.

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    A primeira soma é a dos nn primeiros naturais, n(n+1)2\frac{n(n + 1)}{2}, e o fator 22 cancela seu denominador; a segunda soma nn vezes o número 11.

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    Desenvolvemos o produto; os termos nn e −n-n se anulam.

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    A figura mostra o porquê: cada ímpar é a diferença de dois quadrados consecutivos, o esquadro que converte o quadrado de lado k−1k - 1 no de lado kk.