Exemplo 4.1.1.
A sequência \((x_n)\) dos números naturais ímpares pode ser definida por
\begin{equation*}
x_{n+1}=x_n+2, ~ (n\geq 1), ~ \text{ com } ~ x_1=1.
\end{equation*}
Seção 4.1 Introdução
Muitas sequências são definidas recursivamente (isto é, por recorrência), ou seja, por intermédio de uma regra que permite calcular qualquer termo em função dos antecessores.
Exemplo 4.1.2.
Qualquer progressão aritmética \((x_n)\) de razão \(r\) e o primeiro termo \(a\) pode ser definida por
\begin{equation*}
x_{n+1}=x_n+r, ~ (n\geq 1), ~ \text{ com } ~ x_1=a.
\end{equation*}
Exemplo 4.1.3.
Qualquer progressão geométrica \((x_n)\) de razão \(q\) e o primeiro termo \(a\) pode ser definida por
\begin{equation*}
x_{n+1}=q\times x_n, ~ (n\geq 1), ~ \text{ com } ~ x_1=a.
\end{equation*}
Exemplo 4.1.4.
A sequência \((F_n)\text{,}\) dita de Fibonacci, cujos termos são \(1,1,2,3,5,\ldots\) e na qual cada termo é a soma dos dois imediatamente anteriores, é definida por
\begin{equation*}
F_{n+2} = F_{n+1}+F_n, ~ (n\geq 0), ~ \text{ com } ~ F_1=F_2=1.
\end{equation*}
Nota 4.1.5.
Observe que uma recorrência por si só, não define uma sequência. Para que a sequência fique perfeitamente determinada é necessário também o conhecimento dos primeiros termos.
Observe que, no Exemplo 4.1.1, no Exemplo 4.1.2 e no Exemplo 4.1.3, temos recorrências de primeira ordem, isto é, cada termo é expresso em função do antecessor imediato, e que, no Exemplo 4.1.4, temos uma recorrência de segunda ordem, ou seja, cada termo é expresso em função dos dois antecessores imediatos.
Exemplo 4.1.6.
Quantas são as sequências de 10 termos, pertencentes a \(\{0,1,2\}\text{,}\) que não possuem dois termos consecutivos iguais a 0?
Solução.Chamando de \(x_n\) o número de tais sequências com \(n\) termos, o valor de \(x_{n+2}\) será a soma das seguintes quantidades:
- O número de sequências de \(n+2\) termos que começam por 1 e não possuem dois zeros consecutivos. Isto é precisamente igual a \(x_{n+1}\text{,}\) pois se o primeiro termo é 1, para formar a sequência basta determinar os termos a partir do segundo, o que pode ser feito de \(x_{n+1}\) modos.
- O número de sequências de \(n+2\) termos que começam por 2 e não possuem dois zeros consecutivos. Analogamente, isto é igual a \(x_{n+1}\text{.}\)
- O número de sequências de \(n+2\) termos que começam por 0 e não possuem dois zeros consecutivos. Se o primeiro termo é zero, temos dois modos de escolher o segundo termo (1 ou 2) e, escolhido o segundo termo, temos \(x_n\) modos de escolher os demais. Há, pois, \(2x_n\) sequências começadas em 0.
Logo, \(x_{n+2}=2x_{n+1}+2x_n\text{.}\)
Observe que \(x_1=3\text{,}\) pois, as sequências só possuem um termo, e este termo pode ser qualquer valor do conjunto \(\{0,1,2\}\text{.}\)
Para obter \(x_2\text{,}\) vamos determinar todas as sequências com dois termos que não possuem dois zeros consecutivos:
\begin{equation*}
(0,1), (0,2), (1,0), (2,0), (1,1), (1,2), (2,1), (2,2).
\end{equation*}
Portanto \(x_2=8\text{.}\)
Agora vamos usar o Sage para mostrar que o valor de \(x_{10}\) é 24960.
Exemplo 4.1.7.
Seja \(D_n\) o número de permutações caóticas de \(1,2,\ldots, n\text{,}\) isto é, o número de permutações simples de \(1,2,\ldots, n\text{,}\) nas quais nenhum elemento ocupa o seu lugar primitivo. Mostre que, se \(n\geq 3,\)
\begin{equation*}
D_n = (n-1)\times (D_{n-1}+D_{n-2}).
\end{equation*}
Demonstração.
Vamos separar as permutações caóticas de \(1, 2, 3, \ldots, n\) em dois casos.
1º caso: permutações caóticas em que o elemento que ocupa o primeiro lugar tem seu lugar original ocupado pelo 1.
Como temos \(n-1\) elementos, diferentes do \(1\text{,}\) para cada um deles podemos colocar o elemento na 1ª posição e o número 1 na posição deste número, ou seja, temos \(n-1\) maneiras de fazer isto. Depois disto, os outros elementos podem ser distribuídos de \(D_{n-2}\) formas.
2º caso: permutações caóticas em que o elemento que ocupa o primeiro lugar não tem seu lugar original ocupado pelo 1.
Temos \(n-1\) formas de escolher o elemento que ocupará o primeiro lugar, já que o número 1 não pode ocupar esta posição. Depois disto precisamos contar o número de maneiras de distribuir (de forma caótica) os \(n-1\) elementos nos \(n-1\) lugares, de forma que o número 1 não fique na posição original do número que está na 1ª posição. Para contar esta quantidade, podemos contar o número de permutações caóticas desses \(n-1\) elementos organizados da seguinte maneira: coloque os \(n-2\) elementos em suas posições originais e o número 1 na posição do elemento que está na 1ª posição. O número dessas permutações caóticas é \(D_{n-1}.\)
Como os dois casos são excludentes e cobrem todas as possibilidades, pelo princípio aditivo, temos
\begin{equation*}
D_n = (n-1)\times D_{n-2} + (n-1)\times D_{n-1} = (n-1)\times (D_{n-1}+D_{n-2}).
\end{equation*}
