Sejam
e
(
é chamado de n-ésimo número de Fibonacci). Mostrar que
Passo 1
Beleza, aqui a ideia é provar que, para todo
, vale
A matéria é sobre sequência de Fibonacci e indução matemática. Vamos usar:
1) A definição
2) O princípio da indução (base e passo indutivo).
Passo 2
Base da indução (
):
Lado esquerdo: só temos .
Lado direito: . E
, então
.
Logo , a base funciona.
Lado esquerdo: só temos
Lado direito:
Logo
Passo 3
Hipótese de indução:
Suponha que, para algum , já vale
Suponha que, para algum
Passo 4
Passo indutivo (mostrar para
):
Quero ver que
Quero ver que
Pelo que assumimos (hipótese), a parte até
Mas pela definição de Fibonacci
Logo
que era o que queríamos. Assim, a fórmula vale para todo