[obm-l] 1^2 + 2^2 + ... + n^2

["claudio.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Ontem alguém perguntou aqui na lista como se demonstrava a fórmula da soma dos quadrados dos primeiros n inteiros positivos.

 

Eu diria que 99% das pessoas usaria indução, o que além de ser mecânico e sacal, não ilustra o que realmente ocorre no problema e, o que é pior, se a fórmula não for conhecida (ou seja, se o problema for "deduza a fórmula da soma dos quadrados dos n primeiros inteiros positivos") vai ser difícil adivinhar qual é ela usando apenas indução. Naturalmente, uma vez que você tenha "adivinhado" uma fórmula, possivelmente olhando casos particulares, você pode usar indução para confirmar seu palpite.

 

Eu sempre sou favorável a uma demonstração combinatória, onde contamos o número de elementos de algum conjunto de duas formas distintas.

 

No caso, 1^2 + 2^2 + ... + n^2 é o número de elementos de que conjunto?

 

Por exemplo, considere todos os ternos ordenados (a,b,c) de elementos do conjunto {1,2,...,n,n+1} tais que a > b e a > c.

 

É claro (ou deveria ser pra quem participa dessa lista) que se a = 1, o número de tais ternos é zero, se a = 2, o número é 1*1 = 1, se a = 3, o número é 2*2 = 4. Em geral, se a = k+1, então teremos k possibilidades para b (b pode ser 1, 2, ... ou k) e k para c, de modo que teremos k^2 ternos nas condições do enunciado.

 

Assim, fazendo a variar de 1 a n+1, obteremos o número de ternos nas condições do enunciado: 0^2 + 1^2 + 2^2 + ... + n^2, ou seja, justamente a soma desejada.

 

Agora, um terno nas condições do enunciado só pode ser de três tipos:

(a,b,c) com a > b > c;

(a,b,c) com a > c > b;

(a,b,c) com a > b = c.

 

O número de ternos de cada um dos dois primeiros tipos é igual a:

Binom(n+1,3)  (por que?)

 

O número de ternos do terceiro tipo é Binom(n+1,2)  (por que?).

 

Logo, o número total de ternos nas condições do enunciado é:

2*Binom(n+1,3) + Binom(n+1,2) =

2*(n+1)*n*(n-1)/6 + (n+1)*n/2 =

n*(n+1)*((n-1)/3 + 1/2) =

n*(n+1)*(2n+1)/6.

 

Ou seja, 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2n+1)/6.

 

[]s,

Claudio.