Sequência de números naturais definida recursivamente.

[Chuck Norris]

Considere a sequência de números naturais definida recursivamente por:

\(F_{o}=2;
F_{n}=4.F_{n-1}-3, n\geq 1\)

Prove por indução que:
\(F_{n}=4^{n}+1,\)∀n ≥ 0

[João P. Ferreira]

Indução

1. A base: mostrar que o enunciado vale para \(n = 0\)

2. O passo indutivo: mostrar que, se o enunciado vale para \(n=k\), então o mesmo enunciado vale para \(n=k+1\)

1. para \(n=0\)

\(F_0= 4^0+1={1+1}=2\)

provado

2. \(F_{n}=4^{n}+1 \Rightarrow F_{n+1}=4^{n+1}+1 \\)

\(F_{n+1}=4^{n+1}+1 \Leftrightarrow
F_{n+1}=4.4^n+1 \Leftrightarrow
F_{n+1}=4.4^n+4-3 \Leftrightarrow
F_{n+1}=4.(4^n+1)-3 \Leftrightarrow
F_{n+1}=4.F_{n}-3 \Leftrightarrow\)

c.q.d