Exercício Resolvido - Somatório de N² = 1² + 2² + 3² + ... + n² ou ∑(n^2) = 1^2 + 2^2 + 3^2 + ... + n^2
Ache uma equação para calcular o somatório de N² = 1² + 2² + 3² + ... + n², sendo n um número inteiro.
Solução:
O cálculo de ∑n² pode ser feito de várias formas. Tentarei demonstrar algumas:
Solução:
O cálculo de ∑n² pode ser feito de várias formas. Tentarei demonstrar algumas:
1º método:
Sabendo que:
(n+1)³ - n³ = (n³ + 3n² + 3n + 1) - n³ = 3n² + 3n + 1
Assim:
∑[(p+1)³ - p³] = ∑[3p² + 3p + 1]
Mas:
∑[(p+1)³ - p³] = (2³ - 1³) + (3³ - 2³) + ... + [(n+1)³ - n³]
Perceba que o primeiro termo de cada parênteses é cancelado com o segundo do parênteses seguinte, sobrando apenas:
(n+1)³ - 1³
Então:
(n+1)³ - 1 = ∑[3p² + 3p + 1]
Mas:
∑[3p² + 3p + 1] = ∑3p² + ∑3p + ∑1 = 3*∑p² + 3*∑p + (1+1+1+1+1+...+1)
∑p = 1 + 2 + 3 + 4 + .. + n -> (PA)
∑p = (1+n)*(n/2)
Temos também que:
∑1 = n
Assim:
(n+1)³ - 1 = ∑[3p² + 3p + 1]
(n+1)³ - 1 = 3*∑p² + 3*(1+n)*(n/2) + n
n³ + 3n² + 3n = 3*∑p² + 3n/2 + 3n²/2 + n
3*∑p² = n³ + 3n²/2 + n/2
∑p² = (1/6)*[2n³ + 3n² + n] = (1/6)*n*(n+1)*(2n+1)
2º método:
Usando o triângulo de Pascal:
Imagem retirada do livro Algorithmic Information heory, de G. Chaitin
Como o que queremos é o somatório:
1 + 4 + 9 + 16 + ... + n²
Se observarmos no triângulo acima a terceira coluna, o primeiro termo dela (1), é 1², se somarmos o primeiro ao segundo, temos 1+3 = 4, se somarmos o segundo ao terceiro, temos 3+6 = 9, o terceiro ao quarto 6+10 = 16 ....
Ou seja, a soma dois a dois dos termos da coluna, formam exatamente os termos da sequência que queremos:
Assim:
Ou, agrupado de forma melhor:
.png)
Mas, pelo teorema das colunas, que diz que:
.png)
Temos:
.png)
e
.png)
Tendo, por fim:
1² + 2² + 3² + 4² + ... + n² = (1/6)*n*(n+1)*(n-1 + n+2) = (1/6)*n*(n+1)*(2n+1)
3º método:
Digamos que a gente já conheça o resultado, mas desejamos provar que ele vale pelo método da indução finita :
Se n = 1:
1² = (1/6)*1*(1+1)*(2+1) = 1 Ok, é válido
Agora, a gente supõe que para n = k-1, a fórmula também é válida, admitimos então que:
1² + 2² + 3² + ... + (k-1)² = (1/6)*(k-1)*[(k-1)+1]*[2(k-1)+1] = (1/6)*(k-1)*k*(2k-1)
Supondo que a fórmula acima seja correta, devemos provar que vale para n = k também:
1² + 2² + 3² + 4² + ... + (k-1)² + k² = [(1/6)*(k-1)*k*(2k-1)] + k²
1² + 2² + 3² + 4² + ... + (k-1)² + k² = [(1/6)*(k²-k)*(2k-1)] + k²
1² + 2² + 3² + 4² + ... + (k-1)² + k² = [(1/6)*(2k³ - k² - 2k² + k)] + k²
Fazendo o mínimo múltiplo comum, ou seja, transformando k² = (6/6)*k² temos:
1² + 2² + 3² + 4² + ... + (k-1)² + k² = (1/6)*(2k³ - 3k² + k + 6k²) =
1² + 2² + 3² + 4² + ... + (k-1)² + k² = (1/6)*(2k³ + 3k² + k)
1² + 2² + 3² + 4² + ... + (k-1)² + k² = (1/6)*k*(k+1)*(2k+1)
que é a fórmula (1/6)*n*(n+1)*(2n+1) para n = k. Logo, esta provado por indução.
