Question

Encontre a fórmula fechada da seguinte relação de recorrência:
a(1)=2
a(n)=2*a(n-1) + 1

Answer 1

Resposta:

aₙ = 3 · 2ⁿ⁻¹ - 1

Explicação passo a passo:

É dada a seguinte relação de recorrência:

$\begin{cases}a_1=2\\a_n=2a_{n-1}+1\end{cases}$

Vamos analisar a fórmula da segunda linha para outros termos da sequência:

$a_{n}\;\;\;\,=2a_{n-1}+1\\\\a_{n-1}=2a_{n-2}+1\\\\a_{n-2}=2a_{n-3}+1\\\\...\\\\a_{2}\;\;\;\,=2a_{1}+1$

Podemos manipular as equações acima, a fim de eliminar os termos intermediários da sequência. Por exemplo, se multiplicarmos a segunda equação por 2 e a somarmos com a primeira, teremos:

$+\underline{\begin{cases}a_{n}\;\;\;\;\,\,=2a_{n-1}+1\\2a_{n-1}=2^2a_{n-2}+2\end{cases}}\\\\~~~~~~a_n\;\;\;\,\;\,=2^2a_{n-2}+(1+2)$

Assim, obtivemos a(n) em função de a(n-2). Como o termo que conhecemos é a(1), queremos a(n) em função de a(1). Dessa forma, vamos executar um procedimento parecido com as linhas posteriores, para que a soma dessas linhas resulte na relação entre os termos que queremos. Veja:

$\begin{cases}a_{n}~~~~~~~~~=2a_{n-1}+1\\\\2\cdot(a_{n-1})=2\cdot(2a_{n-2}+1)\\\\2^2\cdot(a_{n-2})=2^2 \cdot(2a_{n-3}+1)\\\\...\\\\2^{n-2}\cdot(a_{2})=2^{n-2}\cdot(2a_{1}+1)\end{cases}\Longrightarrow \begin{cases}a_{n}~~~~~=2a_{n-1}+1\\\\2a_{n-1}=2^2a_{n-2}+2\\\\2^2a_{n-2}=2^3a_{n-3}+2^2\\\\...\\\\2^{n-2}a_{2}=2^{n-1}a_{1}+2^{n-2}\end{cases}$

Note que, agora, quando somarmos as linhas, vamos cancelar os termos intermediários:

$+\underline{\begin{cases}a_{n}~~~~~=\diagup\!\!\!\!\!\!2a_{n-1}+1\\\\\diagup\!\!\!\!\!\!2a_{n-1}=\diagup\!\!\!\!\!\!2^2a_{n-2}+2\\\\\diagup\!\!\!\!\!\!2^2a_{n-2}=\diagup\!\!\!\!\!\!2^3a_{n-3}+2^2\\\\...\\\\\diagup\!\!\!\!\!\!2^{n-2}a_{2}=2^{n-1}a_{1}+2^{n-2}\end{cases}}\\\\~~~~~~\boxed{a_n~~~~~=2^{n-1}a_1+(1+2+2^2+...+2^{n-2})}$

Estamos quase lá. Agora vamos usar o valor dado de a(1)=2:

$a_n=2^{n-1}a_1+(1+2+2^2+...+2^{n-2})}\\\\a_n=2^{n-1}\cdot2+(1+2+2^2+...+2^{n-2})}\\\\a_n=2^{n}+(1+2+2^2+...+2^{n-2})}$        

Já conseguimos uma fórmula fechada, mas podemos simplificá-la. Vê-se que o termo entre parênteses é a soma dos termos de uma PG cuja razão é 2. Usando a fórmula da soma dos termos da PG, temos:

$a_n=2^n+\left(1\cdot\dfrac{2^{n-1}-1}{2-1}\right)\\\\a_n = 2^n+2^{n-1}-1\\\\a_n=2^{n-1}(2+1)-1\\\\\boxed{\boxed{a_n=3\cdot2^{n-1}-1}}$