UFRPE-DM Introdução

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.1.

🔗

A sequência

(x_{n})

dos números naturais ímpares pode ser definida por

x_{n + 1} = x_{n} + 2, (n \geq 1), com x_{1} = 1.

🔗

Exemplo 4.1.2.

🔗

Qualquer progressão aritmética

(x_{n})

de razão

r

e o primeiro termo

a

pode ser definida por

x_{n + 1} = x_{n} + r, (n \geq 1), com x_{1} = a .

🔗

Exemplo 4.1.3.

🔗

Qualquer progressão geométrica

(x_{n})

de razão

q

e o primeiro termo

a

pode ser definida por

x_{n + 1} = q \times x_{n}, (n \geq 1), com x_{1} = a .

🔗

Exemplo 4.1.4.

🔗

A sequência

(F_{n}),

dita de Fibonacci, cujos termos são

1, 1, 2, 3, 5, \dots

e na qual cada termo é a soma dos dois imediatamente anteriores, é definida por

F_{n + 2} = F_{n + 1} + F_{n}, (n \geq 0), com F_{1} = F_{2} = 1.

🔗

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},

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},$ 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} .$
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, $2 x_{n}$ sequências começadas em 0.

Logo,

x_{n + 2} = 2 x_{n + 1} + 2 x_{n} .

Observe que

x_{1} = 3,

pois, as sequências só possuem um termo, e este termo pode ser qualquer valor do conjunto

{0, 1, 2} .

Para obter

x_{2},

vamos determinar todas as sequências com dois termos que não possuem dois zeros consecutivos:

(0, 1), (0, 2), (1, 0), (2, 0), (1, 1), (1, 2), (2, 1), (2, 2) .

Portanto

x_{2} = 8 .

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, \dots, n,

isto é, o número de permutações simples de

1, 2, \dots, n,

nas quais nenhum elemento ocupa o seu lugar primitivo. Mostre que, se

n \geq 3,

D_{n} = (n - 1) \times (D_{n - 1} + D_{n - 2}) .

🔗

Demonstração.

Vamos separar as permutações caóticas de

1, 2, 3, \dots, 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,

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

D_{n} = (n - 1) \times D_{n - 2} + (n - 1) \times D_{n - 1} = (n - 1) \times (D_{n - 1} + D_{n - 2}) .

Matemática Discreta: notas de aula

[search-results-heading]: