Matemática do ensino médio · Grades 10–12

13Sequências: um primeiro curso

Uma sequência é uma lista de números produzida por uma regra: os saldos sucessivos de uma poupança, o tamanho de uma população ano após ano. Este capítulo estuda as duas famílias que dominam as aplicações — as progressões aritméticas, que crescem por passos iguais, e as progressões geométricas, que crescem por razões iguais. A teoria rigorosa dos limites é desenvolvida no Capítulo 20.

13.1 Definir uma sequência

Definição 13.1 (Sequência)

Uma sequência $(u_n)$ associa a cada inteiro $n \geq 0$ (ou $n \geq 1$ ) um número real $u_n$ , seu termo de índice $n$ . Uma sequência pode ser dada

de forma explícita, por uma fórmula de $u_n$ em função de $n$ : por exemplo, $u_n = n^2 + 1$ ;
de forma recursiva, pelo primeiro termo e por uma regra para passar de cada termo ao seguinte: por exemplo, $u_0 = 3$ e $u_{n+1} = 2u_n - 1$ .

Exemplo 13.2

Para $u_n = n^2 + 1$ : $u_0 = 1$ , $u_1 = 2$ , $u_2 = 5$ e $u_{10} = 101$ diretamente. Para $u_0 = 3$ , $u_{n+1} = 2u_n - 1$ : $u_1 = 5$ , $u_2 = 9$ , $u_3 = 17$ — cada termo precisa do anterior; chegar a $u_{10}$ exige dez passos (ou uma fórmula geral, veja o Exercício 13.11).

13.2 Progressões aritméticas

Definição 13.3 (Progressão aritmética)

Uma sequência é uma progressão aritmética de razão $d$ se cada termo é obtido do anterior somando-se $d$ :

u_{n+1} = u_n + d \quad \text{para todo } n.

Equivalentemente: a diferença $u_{n+1} - u_n$ é constante, igual a $d$ .

Teorema 13.4 (Termo geral)

Se $(u_n)$ é uma progressão aritmética de primeiro termo $u_0$ e razão $d$ , então

u_n = u_0 + n\,d \quad \text{para todo } n \geq 0, \qquad\text{e, mais geralmente, } u_n = u_p + (n - p)\,d .

Demonstração. Para ir de $u_0$ a $u_n$ , a regra “some $d$ ” é aplicada $n$ vezes: um passo dá $u_1 = u_0 + d$ , dois passos dão $u_2 = u_0 + 2d$ e, após $n$ passos, cada aplicação contribuiu com um $d$ , de modo que $u_n = u_0 + nd$ . (Esse “e assim por diante” é tornado rigoroso por indução no Capítulo 20.) A fórmula geral segue contando os $n - p$ passos de $u_p$ até $u_n$ . ∎

Teorema 13.5 (Soma de inteiros consecutivos)

Para todo inteiro $n \geq 1$ :

1 + 2 + \dots + n = \frac{n(n+1)}{2}.

Mais geralmente, uma soma de termos consecutivos de uma progressão aritmética vale

(\text{número de termos}) \times \frac{\text{primeiro termo} + \text{último termo}}{2}.

Demonstração. Escreva a soma $S$ duas vezes, a segunda em ordem inversa, e some coluna a coluna:

\begin{array}{ccccccccc} S & = & 1 & + & 2 & + & \dots & + & n\\ S & = & n & + & (n-1) & + & \dots & + & 1\\ \hline 2S & = & (n+1) & + & (n+1) & + & \dots & + & (n+1) \end{array}

Há $n$ colunas, cada uma somando $n + 1$ , logo $2S = n(n+1)$ . Para uma progressão aritmética qualquer o mesmo emparelhamento funciona: primeiro $+$ último $=$ segundo $+$ penúltimo $= \dots$ , porque avançar um passo na ponta esquerda ( $+d$ ) é compensado por recuar um passo na ponta direita ( $-d$ ). ∎

Exemplo 13.6

$1 + 2 + \dots + 100 = \frac{100 \times 101}{2} = 5050$ . A soma dos ímpares $1 + 3 + \dots + 99$ ( $50$ termos) é $50 \times \frac{1 + 99}{2} = 2500$ .

13.3 Progressões geométricas

Definição 13.7 (Progressão geométrica)

Uma sequência é uma progressão geométrica de razão $q \neq 0$ se cada termo é obtido do anterior multiplicando-se por $q$ :

u_{n+1} = q\,u_n \quad \text{para todo } n.

Equivalentemente, quando nenhum termo se anula: o quociente $\frac{u_{n+1}}{u_n}$ é constante, igual a $q$ .

Teorema 13.8 (Termo geral)

Se $(u_n)$ é uma progressão geométrica de primeiro termo $u_0$ e razão $q$ , então

u_n = u_0\, q^n \quad \text{para todo } n \geq 0, \qquad\text{e, mais geralmente, } u_n = u_p\, q^{\,n-p} .

Demonstração. Mesma contagem de passos do Teorema 13.4: de $u_0$ a $u_n$ , a regra “multiplique por $q$ ” é aplicada $n$ vezes, contribuindo com um fator $q^n$ . ∎

Teorema 13.9 (Soma geométrica)

Para todo real $q \neq 1$ e todo inteiro $n \geq 0$ :

1 + q + q^2 + \dots + q^n = \frac{1 - q^{\,n+1}}{1 - q}.

Demonstração. Seja $S = 1 + q + \dots + q^n$ . Multiplique por $q$ : $qS = q + q^2 + \dots + q^{n+1}$ . Subtraia:

S - qS = \bigl(1 + q + \dots + q^n\bigr) - \bigl(q + q^2 + \dots + q^{n+1}\bigr) = 1 - q^{\,n+1},

porque cada termo intermediário aparece uma vez em cada soma e se cancela. Logo $(1 - q)S = 1 - q^{\,n+1}$ e, dividindo por $1 - q \neq 0$ , obtém-se a fórmula. ∎

Exemplo 13.10

$1 + 2 + 4 + \dots + 2^{10} = \frac{1 - 2^{11}}{1 - 2} = 2^{11} - 1 = 2047$ : dobrar grãos de arroz nas casas de um tabuleiro de xadrez esgota qualquer celeiro muito antes da $64^{\text{a}}$ casa, em que o total é $2^{64} - 1 \approx 1.8 \times 10^{19}$ .

Passos iguais contra razões iguais: uma progressão aritmética (u_n+1 = u_n + 0.9, em azul) segue uma reta; uma progressão geométrica (u_n+1 = 1.2\,u_n, em vermelho) segue uma curva exponencial que acaba ultrapassando-a. — Passos iguais contra razões iguais: uma progressão aritmética ( $u_{n+1} = u_n + 0.9$ , em azul) segue uma reta; uma progressão geométrica ( $u_{n+1} = 1.2\,u_n$ , em vermelho) segue uma curva exponencial que acaba ultrapassando-a.

Método 13.11 (Reconhecer o tipo de uma sequência)

Calcule $u_{n+1} - u_n$ e simplifique. Se o resultado for uma constante $d$ , a sequência é uma progressão aritmética. Caso contrário, calcule $\frac{u_{n+1}}{u_n}$ (termos não nulos) e simplifique: uma constante $q$ indica progressão geométrica. Se nenhum dos dois for constante, a sequência não é de nenhum dos dois tipos — nunca conclua apenas a partir dos primeiros termos.

Exemplo 13.12

Para $u_n = 3 \times 5^n$ : $\frac{u_{n+1}}{u_n} = \frac{3 \times 5^{n+1}}{3 \times 5^n} = 5$ para todo $n$ : progressão geométrica de razão $5$ . Para $u_n = n^2$ : $u_1 - u_0 = 1$ , mas $u_2 - u_1 = 3$ , e $\frac{u_1}{u_0}$ nem sequer está definido — não é aritmética nem geométrica.

13.4 Monotonicidade

Definição 13.13 (Sequência monótona)

Uma sequência $(u_n)$ é crescente se $u_{n+1} \geq u_n$ para todo $n$ , e decrescente se $u_{n+1} \leq u_n$ para todo $n$ .

Método 13.14 (Estudar a monotonicidade)

Estude o sinal de $u_{n+1} - u_n$ . Para sequências de termos positivos, pode-se, em vez disso, comparar $\frac{u_{n+1}}{u_n}$ com $1$ .

Exemplo 13.15

Uma progressão aritmética é crescente quando $d \geq 0$ ( $u_{n+1} - u_n = d$ ) e decrescente quando $d \leq 0$ . Uma progressão geométrica com $u_0 > 0$ e $q > 1$ é crescente: $u_{n+1} - u_n = u_0 q^n (q - 1) > 0$ ; com $u_0 > 0$ e $0 < q < 1$ ela é decrescente.

13.5 Comportamento a longo prazo, informalmente

O que acontece com $u_n$ quando $n$ fica muito grande? Para uma progressão aritmética com $d > 0$ , os termos $u_0 + nd$ acabam ultrapassando qualquer número fixado. Para uma progressão geométrica com $0 < q < 1$ , os termos $u_0 q^n$ encolhem rumo a $0$ : multiplicar repetidamente por $0.9$ , digamos, corrói qualquer valor inicial. E, para $q > 1$ , os termos explodem, como no Exemplo 13.10.

Observação 13.16

Essas afirmações podem ser tornadas perfeitamente precisas — “os termos acabam ficando a qualquer distância dada de $0$ ” — e demonstradas. Essa é a teoria dos limites, o tema de abertura do Capítulo 20.

13.6 Exercícios

Exercício 13.1 ★

Para cada sequência, calcule $u_1$ , $u_2$ , $u_3$ :

u_n = \frac{n}{n+1}; \qquad u_0 = 5,\ u_{n+1} = 3u_n - 2; \qquad u_n = (-1)^n\,n .

Solução

Solução de Exercício 13.1.

$u_n = \frac{n}{n+1}$ : $u_1 = \frac12$ , $u_2 = \frac23$ , $u_3 = \frac34$ .

$u_0 = 5$ , $u_{n+1} = 3u_n - 2$ : $u_1 = 13$ , $u_2 = 37$ , $u_3 = 109$ .

$u_n = (-1)^n n$ : $u_1 = -1$ , $u_2 = 2$ , $u_3 = -3$ .

Exercício 13.2 ★

$(u_n)$ é uma progressão aritmética com $u_0 = 7$ e $d = -3$ . Calcule $u_{10}$ e $u_{25}$ . $(v_n)$ é uma progressão aritmética com $v_3 = 11$ e $v_8 = 26$ . Encontre a razão e $v_0$ .

Solução

Solução de Exercício 13.2.

$u_{10} = 7 + 10 \times (-3) = -23$ e $u_{25} = 7 - 75 = -68$ .

Para $(v_n)$ : $v_8 = v_3 + 5d$ dá $26 = 11 + 5d$ , logo $d = 3$ ; então $v_0 = v_3 - 3d = 11 - 9 = 2$ .

Exercício 13.3 ★

$(u_n)$ é uma progressão geométrica com $u_0 = 5$ e $q = 2$ . Calcule $u_8$ . $(v_n)$ é uma progressão geométrica de termos positivos, com $v_2 = 12$ e $v_4 = 48$ . Encontre a razão e $v_0$ .

Solução

Solução de Exercício 13.3.

$u_8 = 5 \times 2^8 = 1280$ .

Para $(v_n)$ : $v_4 = v_2\, q^2$ dá $48 = 12 q^2$ , logo $q^2 = 4$ e $q = 2$ (os termos são positivos). Então $v_0 = \frac{v_2}{q^2} = \frac{12}{4} = 3$ .

Exercício 13.4 ★

Calcule

1 + 2 + 3 + \dots + 500, \qquad 4 + 7 + 10 + \dots + 61, \qquad 1 + \frac12 + \frac14 + \dots + \frac{1}{2^{10}} .

Solução

Solução de Exercício 13.4.

$1 + \dots + 500 = \frac{500 \times 501}{2} = 125\,250$ .

$4 + 7 + \dots + 61$ é uma progressão aritmética com $d = 3$ e $\frac{61 - 4}{3} + 1 = 20$ termos: soma $20 \times \frac{4 + 61}{2} = 650$ .

$1 + \frac12 + \dots + \frac{1}{2^{10}}$ é geométrica com $q = \frac12$ e $11$ termos: $\frac{1 - (1/2)^{11}}{1 - 1/2} = 2\left(1 - \frac{1}{2048}\right) = \frac{2047}{1024}$ .

Exercício 13.5 ★

Determine se cada sequência é uma progressão aritmética, uma progressão geométrica ou nenhuma das duas:

u_n = 4n - 1; \qquad v_n = \frac{2^n}{3^{n+1}}; \qquad w_n = n^2 + n .

Solução

Solução de Exercício 13.5.

$u_{n+1} - u_n = 4(n+1) - 1 - 4n + 1 = 4$ : progressão aritmética com $d = 4$ .

$\frac{v_{n+1}}{v_n} = \frac{2^{n+1}}{3^{n+2}} \cdot \frac{3^{n+1}}{2^n} = \frac23$ : progressão geométrica com $q = \frac23$ .

$w_0 = 0$ , $w_1 = 2$ , $w_2 = 6$ : as diferenças $2$ e $4$ são distintas, logo não é aritmética; $\frac{w_1}{w_0}$ nem sequer está definido, e os quocientes $\frac{w_2}{w_1} = 3 \neq \frac{w_3}{w_2} = 2$ : nenhuma das duas.

Exercício 13.6 ★★

Um teatro tem $20$ fileiras: $16$ poltronas na primeira fileira, e cada fileira tem $2$ poltronas a mais que a anterior. Quantas poltronas há na última fileira? E no teatro inteiro?

Solução

Solução de Exercício 13.6.

Os números de poltronas por fileira formam uma progressão aritmética: primeiro termo $16$ , razão $2$ . A última ( $20^{\text{a}}$ ) fileira tem $16 + 19 \times 2 = 54$ poltronas. O total é $20 \times \frac{16 + 54}{2} = 700$ poltronas.

Exercício 13.7 ★★

Uma população de bactérias dobra a cada hora; ao meio-dia há $500$ bactérias. Quantas há às 20h? Depois de quantas horas inteiras a população ultrapassa um milhão pela primeira vez? (Resolva testando potências sucessivas de $2$ .)

Solução

Solução de Exercício 13.7.

Após $n$ horas a população é $500 \times 2^n$ . Às 20h, $n = 8$ : $500 \times 256 = 128\,000$ bactérias. Precisamos de $500 \times 2^n > 10^6$ , isto é, $2^n > 2000$ : como $2^{10} = 1024$ e $2^{11} = 2048$ , a população ultrapassa um milhão pela primeira vez após $11$ horas inteiras, às 23h.

Exercício 13.8 ★★

Todo mês, um poupador deposita $100$ euros em uma conta que paga $0.2\%$ de juros mensais sobre o saldo existente (os juros são creditados logo antes do depósito). Seja $c_n$ o saldo imediatamente após o $n$ -ésimo depósito, de modo que $c_1 = 100$ e $c_{n+1} = 1.002\,c_n + 100$ . Calcule $c_2$ e $c_3$ e explique por que $(c_n)$ não é progressão aritmética nem geométrica.

Solução

Solução de Exercício 13.8.

$c_2 = 1.002 \times 100 + 100 = 200.20$ e $c_3 = 1.002 \times 200.20 + 100 \approx 300.60$ . As diferenças $c_2 - c_1 = 100.20$ e $c_3 - c_2 \approx 100.40$ não são iguais, logo $(c_n)$ não é aritmética; os quocientes $\frac{c_2}{c_1} = 2.002$ e $\frac{c_3}{c_2} \approx 1.50$ também não são iguais, logo não é geométrica. (Recorrências mistas do tipo “multiplique e some”, como esta, resolvem-se com o truque da sequência auxiliar do Exercício 13.11.)

Exercício 13.9 ★★

Estude a monotonicidade das sequências

u_n = n^2 - 8n \ (n \geq 0), \qquad v_n = \frac{3^n}{n!}\ (n \geq 1),

em que $n! = 1 \times 2 \times \dots \times n$ . (Para $(v_n)$ , compare $\frac{v_{n+1}}{v_n}$ com $1$ .)

Solução

Solução de Exercício 13.9.

$u_{n+1} - u_n = (n+1)^2 - 8(n+1) - n^2 + 8n = 2n - 7$ : negativa para $n \leq 3$ e positiva para $n \geq 4$ . Assim, $(u_n)$ decresce até $u_4 = 16 - 32 = -16$ e depois cresce: não é monótona.

$(v_n)$ tem termos positivos e

\frac{v_{n+1}}{v_n} = \frac{3^{n+1}}{(n+1)!} \cdot \frac{n!}{3^n} = \frac{3}{n+1},

que é $> 1$ para $n \leq 1$ , $= 1$ para $n = 2$ e $< 1$ para $n \geq 3$ : a sequência cresce até $v_2 = v_3 = \frac92$ e depois decresce.

Exercício 13.10 ★★

A soma dos $n$ primeiros termos de uma progressão aritmética com $u_0 = 3$ e $d = 4$ vale $903$ . Encontre $n$ . (Monte uma equação do segundo grau em $n$ e use o Capítulo 10.)

Solução

Solução de Exercício 13.10.

Os $n$ primeiros termos são $u_0, \dots, u_{n-1}$ , com $u_0 = 3$ e $u_{n-1} = 3 + 4(n-1) = 4n - 1$ . Sua soma é

n \times \frac{3 + (4n-1)}{2} = n(2n + 1) = 903,

logo $2n^2 + n - 903 = 0$ . Aqui $\Delta = 1 + 4 \times 2 \times 903 = 7225 = 85^2$ , e $n = \frac{-1 + 85}{4} = 21$ (a raiz negativa é descartada). Verificação: $21 \times 43 = 903$ .

Exercício 13.11 ★★★

Sejam $u_0 = 3$ e $u_{n+1} = 2u_n - 1$ .

Calcule $u_1, u_2, u_3$ e conjecture uma fórmula para $u_n$ .
Seja $v_n = u_n - 1$ . Mostre que $(v_n)$ é uma progressão geométrica e dê sua razão e seu primeiro termo.
Deduza uma fórmula explícita para $u_n$ e verifique sua conjectura.

Solução

Solução de Exercício 13.11.

1. $u_1 = 5$ , $u_2 = 9$ , $u_3 = 17$ : cada termo é uma unidade a mais que $4, 8, 16$ , o que sugere $u_n = 2^{n+1} + 1$ .

2. Com $v_n = u_n - 1$ :

v_{n+1} = u_{n+1} - 1 = 2u_n - 1 - 1 = 2(u_n - 1) = 2v_n,

de modo que $(v_n)$ é uma progressão geométrica de razão $2$ e primeiro termo $v_0 = u_0 - 1 = 2$ .

3. Logo $v_n = 2 \times 2^n = 2^{n+1}$ e $u_n = v_n + 1 = 2^{n+1} + 1$ , o que confirma a conjectura. (O $1$ subtraído em $v_n$ é o ponto fixo de $x \mapsto 2x - 1$ ; a mesma ideia reaparece para $u_{n+1} = au_n + b$ no Capítulo 20.)

13.7 Problema: A torre de Brama e os coelhos de Fibonacci

Problema 13.1

Problema de fim de semana — duas recorrências lendárias: a torre que acaba com o mundo, a sequência que cresce como ouro e o truque auxiliar que domestica empréstimos

Duas sequências reinam no folclore da matemática. Uma conta os movimentos da torre de Brama — sessenta e quatro discos de ouro cuja transferência, diz a lenda, acabará com o mundo. A outra conta os coelhos de Fibonacci e esconde a razão áurea. Nenhuma das duas é aritmética, nenhuma é geométrica — e ambas se rendem às armas deste capítulo: recorrências, somas geométricas (Teorema 13.9) e o truque da sequência auxiliar do Exercício 13.11, que também calcula o seu financiamento.

Parte I — A torre de Brama. O quebra-cabeça: $n$ discos de tamanhos decrescentes estão empilhados no pino A; leve a pilha inteira para o pino C, um disco por vez, sem nunca colocar um disco maior sobre um menor (o pino B pode ajudar). Seja $h_n$ o número mínimo de movimentos.

Jogue (com moedas) e registre $h_1$ , $h_2$ , $h_3$ .
Explique a estratégia por trás da recorrência $h_{n+1} = 2h_n + 1$ : o que precisa acontecer antes e depois de o maior disco se mover?
Resolva a recorrência com o truque do Exercício 13.11: ponha $v_n = h_n + 1$ , mostre que $(v_n)$ é uma progressão geométrica e conclua que $h_n = 2^n - 1$ .
A torre da lenda tem $64$ discos, e os monges movem um disco por segundo. Usando $2^{10} = 1024 \approx 10^3$ , estime o tempo de transferência em anos (um ano tem cerca de $3 \times 10^7$ segundos; compare com o Exemplo 13.10, o mesmo gigante em outra história). Devemos nos preocupar?
Por que nenhuma estratégia consegue menos que $2^n - 1$ movimentos? Argumente que qualquer solução satisfaz $h_{n+1} \geq 2 h_n + 1$ : o que tem de ser verdade sobre os $n$ discos de cima logo antes e logo depois do movimento do disco de baixo?

Parte II — Fibonacci. Defina $F_1 = F_2 = 1$ e $F_{n+2} = F_{n+1} + F_n$ (cada termo é a soma dos dois anteriores — a regra de contagem de ritmos do volume do ensino fundamental, agora com seu nome europeu).

Liste $F_1$ até $F_{12}$ .
Mostre que $(F_n)$ não é progressão aritmética nem geométrica, mas que é estritamente crescente a partir de $n = 2$ (Método 13.14 e a recorrência).
Demonstre a identidade das somas

$F_1 + F_2 + \dots + F_n = F_{n+2} - 1$

por telescopagem: escreva cada $F_k$ como $F_{k+2} - F_{k+1}$ e veja a soma desabar. Verifique-a para $n = 6$ .
Demonstre a identidade dos quadrados $F_1^2 + F_2^2 + \dots + F_n^2 = F_n F_{n+1}$ , telescopando com $F_k F_{k+1} - F_{k-1} F_k = F_k^2$ . Verifique para $n = 4$ . (Imagem: quadrados de lados $1, 1, 2, 3, 5, \dots$ ladrilham um retângulo — o esqueleto da famosa espiral de Fibonacci.)
A identidade de Cassini afirma que $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$ . Verifique-a para $n = 4, 5, 6$ — e reconheça o motor do truque do quadrado que some, jogado no problema sobre áreas do volume do ensino fundamental.
Mostre, a partir da recorrência, que $F_{n+2} \geq 2 F_n$ : Fibonacci pelo menos dobra a cada dois passos — ela cresce pelo menos tão depressa quanto uma progressão geométrica de razão $\sqrt2$ .
Calcule as razões $r_n = \frac{F_{n+1}}{F_n}$ para $n = 3$ até $10$ (três casas decimais). Admitindo que elas se acomodem em um limite $L$ , passe a relação $r_{n+1} = 1 + \frac{1}{r_n}$ ao limite e resolva: que número do Problema 2.1 os coelhos veneram?

Parte III — O truque auxiliar, no banco.

Generalize o Exercício 13.11: para $u_{n+1} = a\,u_n + b$ com $a \neq 1$ , ponha $\ell = \frac{b}{1 - a}$ (o ponto fixo). Mostre que $v_n = u_n - \ell$ é uma progressão geométrica de razão $a$ e conclua que $u_n = a^n (u_0 - \ell) + \ell$ .
Um empréstimo: $10\,000$ euros a $1\,\%$ de juros ao mês, pagos $300$ euros por mês, de modo que a dívida obedece a $d_{n+1} = 1.01\,d_n - 300$ . Aplique a questão 13 (o ponto fixo primeiro!) para obter uma fórmula explícita de $d_n$ .
Com uma calculadora, encontre o primeiro mês em que a dívida se extingue e o total pago. Quanto custou o empréstimo em si?
Uma cidade de $50\,000$ habitantes cresce $2\,\%$ ao ano e ainda recebe $1\,000$ recém-chegados: $p_{n+1} = 1.02\,p_n + 1000$ . Dê a fórmula explícita e a população após $10$ anos.

Parte IV — As duas famílias reais.

Calcule $1 + 2 + 3 + \dots + 1000$ (Teorema 13.5 — a soma do pequeno Gauss, do volume do ensino fundamental, agora oficial) e $1 + 2 + 4 + \dots + 2^{19}$ (Teorema 13.9).
Calcule a soma da progressão aritmética $7, 12, 17, \dots, 502$ (quantos termos?).
Plano de poupança: $100$ euros depositados por mês, rendendo $0.5\,\%$ ao mês; após o $n$ -ésimo depósito o saldo é $100\left(1.005^{n-1} + \dots + 1.005 + 1\right)$ . Calcule o saldo após $5$ anos ( $n = 60$ ).
Final — o kit do domador de sequências: descrições explícitas contra recursivas; as duas famílias reais e suas fórmulas de soma; a sequência auxiliar que transforma recorrências afins em geométricas; e Fibonacci, primeira cidadã fora das duas famílias, domada hoje por identidades e à espera das matrizes (ano 12) e dos limites para a captura completa. Uma frase para cada.

Solução

Solução de Problema 13.1.

1. $h_1 = 1$ , $h_2 = 3$ , $h_3 = 7$ .

2. Para mover o maior disco, os $n$ discos que estão sobre ele precisam antes migrar para o pino livre ( $h_n$ movimentos); o disco grande atravessa ( $1$ movimento); os $n$ discos precisam então subir de volta sobre ele ( $h_n$ movimentos): $h_{n+1} = 2h_n + 1$ .

3. $v_{n+1} = h_{n+1} + 1 = 2h_n + 2 = 2v_n$ : progressão geométrica de razão $2$ com $v_1 = 2$ , logo $v_n = 2^n$ e $h_n = 2^n - 1$ .

4. $2^{64} - 1 \approx 1.8 \times 10^{19}$ segundos; dividindo por $3 \times 10^7$ segundos por ano: cerca de $6 \times 10^{11}$ anos — seiscentos bilhões de anos, quarenta vezes a idade do universo. Os monges podem fazer pausas para o café.

5. Em qualquer solução válida, considere o primeiro movimento do disco de baixo: nesse instante os outros $n$ discos têm de estar todos no único pino restante (no mínimo $h_n$ movimentos para levá-los até lá) e, depois do último movimento do disco de baixo, todos precisam voltar sobre ele (no mínimo mais $h_n$ ): qualquer solução precisa de pelo menos $2h_n + 1$ movimentos. A recorrência é piso e teto ao mesmo tempo: $2^n - 1$ é ótimo.

6. $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$ .

7. Não é aritmética ( $2 - 1 = 1$ , mas $3 - 2 = 1$ e $5 - 3 = 2$ : as diferenças mudam); não é geométrica ( $\frac21 = 2$ , mas $\frac32 = 1.5$ ). Crescente: para $n \geq 2$ , $F_{n+1} - F_n = F_{n-1} > 0$ .

8. $F_k = F_{k+2} - F_{k+1}$ , logo

\sum_{k=1}^{n} F_k = (F_3 - F_2) + (F_4 - F_3) + \dots + (F_{n+2} - F_{n+1}) = F_{n+2} - F_2 = F_{n+2} - 1 .

Para $n = 6$ : $1 + 1 + 2 + 3 + 5 + 8 = 20 = F_8 - 1 = 21 - 1$ .

9. $F_k F_{k+1} - F_{k-1} F_k = F_k (F_{k+1} - F_{k-1}) = F_k \cdot F_k = F_k^2$ ; a soma telescopa até $F_n F_{n+1} - F_1 F_0$ (com $F_0 = 0$ ): a soma dos quadrados é $F_n F_{n+1}$ . Para $n = 4$ : $1 + 1 + 4 + 9 = 15 = F_4 F_5 = 3 \times 5$ .

10. $F_5 F_3 - F_4^2 = 5 \times 2 - 9 = 1$ ; $F_6 F_4 - F_5^2 = 8 \times 3 - 25 = -1$ ; $F_7 F_5 - F_6^2 = 13 \times 5 - 64 = 1$ : alternando $\pm 1$ . Essa diferença de uma unidade entre $F_{n+1} F_{n-1}$ e $F_n^2$ é exatamente o quadradinho ganho ou perdido do mágico: recortar um quadrado $F_n \times F_n$ em peças remontadas como um retângulo $F_{n+1} \times F_{n-1}$ tem de criar ou engolir uma unidade — a fresta.

11. $F_{n+2} = F_{n+1} + F_n \geq F_n + F_n = 2F_n$ (a sequência é crescente): a cada dois índices, pelo menos uma duplicação — crescimento pelo menos geométrico, de razão $\sqrt2$ por índice.

12. $1.5$ ; $1.667$ ; $1.6$ ; $1.625$ ; $1.615$ ; $1.619$ ; $1.618$ ; $1.618$ . Se $r_n \to L$ : de $F_{n+2} = F_{n+1} + F_n$ , dividindo por $F_{n+1}$ , $r_{n+1} = 1 + \frac{1}{r_n}$ , logo $L = 1 + \frac1L$ , isto é, $L^2 = L + 1$ : $L = \varphi = \frac{1 + \sqrt5}{2}$ , a razão áurea do Problema 2.1. Os coelhos multiplicam-se em ouro.

13. $v_{n+1} = u_{n+1} - \ell = a u_n + b - \ell$ ; como $\ell = a\ell + b$ , isso é $a(u_n - \ell) = a v_n$ : progressão geométrica de razão $a$ . Logo $v_n = a^n v_0$ e $u_n = a^n (u_0 - \ell) + \ell$ .

14. Ponto fixo: $\ell = 1.01\ell - 300$ dá $\ell = 30\,000$ . Assim, $d_n = 1.01^n (10\,000 - 30\,000) + 30\,000 = 30\,000 - 20\,000 \times 1.01^n$ .

15. $d_n \leq 0$ exige $1.01^n \geq 1.5$ : $1.01^{40} \approx 1.489$ e $1.01^{41} \approx 1.504$ : a $41^{\text{a}}$ prestação liquida a dívida (e é um pouco menor que $300$ ). Total pago: pouco menos de $41 \times 300 = 12\,300$ euros — os $10\,000$ emprestados custaram cerca de $2\,300$ euros de juros.

16. Ponto fixo $\ell = \frac{1000}{1 - 1.02} = -50\,000$ , logo $p_n = 1.02^n \times 100\,000 - 50\,000$ . Após $10$ anos: $1.02^{10} \approx 1.219$ : $p_{10} \approx 71\,900$ habitantes.

17. $\frac{1000 \times 1001}{2} = 500\,500$ ; e $2^{20} - 1 = 1\,048\,575$ .

18. De $7$ até $502$ em passos de $5$ : $\frac{502 - 7}{5} + 1 = 100$ termos; soma $= 100 \times \frac{7 + 502}{2} = 25\,450$ .

19. Saldo $= 100 \times \frac{1.005^{60} - 1} {1.005 - 1} \approx 100 \times \frac{0.3489}{0.005} \approx 6\,977$ euros — dos quais $6\,000$ depositados e cerca de $977$ rendidos: as somas geométricas são a língua materna do banco.

20. As fórmulas explícitas respondem na hora “quanto vale $u_{1000}$ ”; as recorrências descrevem como os sistemas de fato evoluem — a arte é converter as segundas nas primeiras. As progressões aritméticas somam, as geométricas multiplicam, e cada família tem sua fórmula de soma (o emparelhamento de Gauss; o truque da duplicação). O truque do ponto fixo com sequência auxiliar converte toda recorrência afim em uma geométrica — empréstimos, populações e a torre caíram todos diante dele. Fibonacci não obedece a nenhuma das famílias e, no entanto, identidades telescópicas capturaram suas somas e seus quadrados; seu retrato completo (uma fórmula exata, o limite áureo) aguarda ferramentas mais fortes.