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.
