Sejam
e
naturais. Encontre uma fórmula de recorrência para
Mostre que
onde
é um polinômio de grau
, cujo termo de maior grau é
.
Passo 1
O que o enunciado pede e o que nos é dado:
- Pede-se uma fórmula de recorrência para
onde
e
são naturais.
- Pede-se também mostrar que
onde
é um polinômio em
de grau
e cujo termo de maior grau é
.
Informações importantes que vamos usar (já claras no enunciado):
-
, . - A soma começa em
e vai até . - Não há dados numéricos específicos; a solução deve ser válida para todo
naturais.
Passo 2
Definição e notação útil: vamos definir
Observação simples de caso-base: para
temos
Isso nos dá o ponto inicial para uma recorrência.
Agora lembramos o enunciado do binômio de Newton (expansão de
). Para qualquer inteiro
,
Subtraindo
dos dois lados, obtemos a identidade de diferença
Essa identidade é fundamental porque transforma potências em uma soma de potências de grau menor — ideia básica de “diferença discreta”.
Passo 3
Agora vamos somar a identidade do passo anterior para
. Fazendo isso, o lado esquerdo telescopa:
No lado direito podemos trocar as somas (soma dupla) e usar a definição
(repare que somar de
a
inclui o termo
que é zero quando
, e o caso
dá
mas isso será tratado naturalmente):
pois
(o
só contribui zero para
; para
temos
, consistente).
Portanto obtemos a identidade-chave
Passo 4
Isolando
nessa identidade, notando que
, temos
Logo a fórmula de recorrência pedida é
Isso expressa a soma de potências de grau
em termos de
e das somas
com
. É uma recorrência em
(e vale para todo
).
Passo 5
Interpretação prática e caso base: a recorrência liga
a
. Já conhecemos
. Assim, por indução em
pode-se calcular
sucessivamente. Vou mostrar rapidamente o uso para obter a fórmula clássica de
para ilustrar como a recorrência funciona:
Para
, a recorrência dá
Como
e
,
que é a fórmula conhecida (bom sinal de que a recorrência está correta).
Passo 6
Provar que
é um polinômio em
de grau
com termo principal
.
Faremos por indução em
.
Base
:
é um polinômio de grau
e o termo de maior grau é
. OK.
Passo indutivo: suponha que para todo
a função
é um polinômio em
de grau
e cujo coeficiente líder é
, isto é, o termo de maior grau de
é
.
Olhemos a recorrência do Passo 4:
Pelo hipótese indutiva cada
(com
) é polinomial de grau
. O termo
é um polinômio de grau
. Assim o lado direito é combinação linear de polinômios, portanto é polinomial; mais precisamente, tem grau exatamente
porque nenhum dos
com
contém termo
(o maior grau de
é
), enquanto
tem termo
com coeficiente
. Assim o termo
do numerador é simplesmente
(os outros somandos não contribuem para
), e ao dividir por
obtemos coeficiente líder
.
Portanto
é um polinômio em
de grau
cujo coeficiente do termo
é
. Isso completa a prova por indução.
Passo 7
Observações finais e ligação com fórmulas conhecidas:
- A recorrência do Passo 4 permite calcular explicitamente
para qualquer usando as fórmulas já obtidas para potências menores. Por exemplo: -
. - Usando a recorrência para
e obtém-se .
-
- A declaração que
é um polinômio de grau com termo dominante é uma forma elementar do que, em termos mais avançados, é conhecido como a fórmula de Faulhaber (que descreve essas somas por polinômios, cujos coeficientes podem ser expressos usando números de Bernoulli). Aqui provamos apenas a existência e o termo principal; a recorrência dá uma maneira construtiva de encontrar todos os coeficientes sem recorrer imediatamente aos números de Bernoulli.