Recorrencias
Muitas sequências não aparecem por fórmula direta, mas por uma regra que liga cada termo aos anteriores. O trabalho aqui e entender o mecanismo da passagem, não só calcular terminho por terminho.
Modelos clássicos
- Linear de 1a ordem an+1 = an + r produz PA
- Multiplicativa an+1 = q an produz PG
- Fibonacci an+2 = an+1 + an
Recorrencias lineares e ponto fixo
Recorrencias do tipo an+1 = p an + b ficam muito mais claras quando deslocamos a sequência para o ponto fixo, isto e, o valor que ficaria parado se a regra fosse aplicada indefinidamente.
Modelo afim
- Recorrencia an+1 = p an + b
- Ponto fixo L = pL + b, logo L = b/(1-p), se p ≠ 1
- Troca un = an - L
- Resultado un+1 = p un, ou seja, vira uma PG
Exemplo
Resolva a1=5 e an+1=2an+3.
1
O ponto fixo satisfaz L = 2L + 3, então L=-3.
2
Defina un = an + 3.
3
Então un+1 = 2un e u1 = 8.
an = 8*2n-1 - 3.
Inducao matemática
Inducao e a técnica-padrão para provar fórmulas validas para todo natural. A ideia e verificar o primeiro caso e, depois, mostrar que a verdade de um passo empurra a verdade do seguinte.
Estrutura da prova
- Base mostre que a proposicao vale no primeiro caso
- Hipótese assuma que vale para n
- Passo prove para n+1 usando a hipótese
Exercício rápido
Cheque rápido
Numa prova por inducao, o que vem primeiro?