Os números de Fibonacci são definidos recursivamente pela sequência Fn onde F0=0, F1=1 e para n >= 2, Fn=Fn-1+Fn-2.
Aqui, examinamos as propriedades dos números de Fibonacci.
Encontre uma fórmula fechada para a sequência de Fibonacci usando as seguintes etapas.
Considere a sequência definida recursivamente (xn) onde x0=c e xn+1=a xn. Mostre que essa sequência pode ser descrita pela fórmula fechada xn=c a^n para todo n >= 0.

Passo 1

O enunciado define a sequência por x0 = c e xn+1 = a,xn e pede uma fórmula fechada. O conteúdo aqui é recorrência de primeira ordem e a ferramenta que vamos usar é o princípio de indução matemática.

Passo 2

Base da indução: para n=0 temos x0 = c. Por outro lado, c,a^0 = c, logo a fórmula xn = c,a^n vale para n=0.

Passo 3

Hipótese de indução: suponha que, para algum k>=0, valha xk = c,a^k.

Passo 4

Passo indutivo: usando a recorrência, xk+1 = a,xk = a,(c,a^k) = c,a^k+1Assim mostramos que, se vale para k, vale também para k+1.

Passo 5

Pelo princípio de indução, a fórmula fechada xn = c,a^n é válida para todo n>=0.

Resposta

xn = c,a^n para todo n>=0.

Exercícios relacionados