Seção 4.2 Recorrências Lineares de Primeira Ordem
Exemplo 4.2.2.
As recorrências \(x_{n+1}=2x_n-n^2\) e \(x_{n+1}=nx_n\) são lineares e a recorrência \(x_{n+1}=x_n^2\) não é linear. As duas últimas são ditas homogêneas, por não possuírem termo independente de \(x_n\text{.}\)
Agora vamos resolver algumas recorrências lineares homogêneas de primeira ordem.
Exemplo 4.2.3.
Resolva a recorrência \(x_{n+1}=nx_n, x_1=1.\)
Solução.Temos
\begin{align*}
x_2 = \amp ~ 1x_1\\
x_3 = \amp ~ 2x_2\\
x_4 = \amp ~ 3x_3\\
\vdots~~ = \amp ~~~~ \vdots\\
x_n = \amp ~ (n-1)x_{n-1}.
\end{align*}
Daí, multiplicando, obtemos
\begin{equation*}
x_n = (n-1)!x_1.
\end{equation*}
Como \(x_1=1\text{,}\) temos \(x_n=(n-1)!.\)
Exemplo 4.2.4.
Resolva a recorrência \(x_{n+1}=2x_n.\)
Solução.Temos
\begin{align*}
x_2 = \amp ~ 2x_1\\
x_3 = \amp ~ 2x_2\\
x_4 = \amp ~ 2x_3\\
\vdots~~ = \amp ~~~~ \vdots\\
x_n = \amp ~ 2x_{n-1}.
\end{align*}
Daí, multiplicando, obtemos
\begin{equation*}
x_n = 2^{n-1}x_1.
\end{equation*}
Como não foi definido o valor de \(x_1\text{,}\) há uma infinidade de soluções para a recorrência,
\begin{equation*}
x_n = C\cdot 2^{n-1},
\end{equation*}
na qual, \(C\) é uma constante arbitrária.
Nota 4.2.5.
As recorrências lineares não-homogêneas de primeira ordem que mais facilmente se resolvem são as da forma \(x_{n+1}=x_n+f(n)\text{.}\)
Com efeito, temos
\begin{align*}
x_2 = \amp ~ x_1 + f(1)\\
x_3 = \amp ~ x_2 + f(2)\\
x_4 = \amp ~ x_3 + f(3)\\
\vdots~~ = \amp ~~~~ \vdots\\
x_n = \amp ~ x_{n-1} + f(n-1).
\end{align*}
Somando, obtemos
\begin{equation*}
x_n=x_1+\sum_{k=1}^{n-1}f(k).
\end{equation*}
Exemplo 4.2.6.
Resolva a recorrência \(x_{n+1}=x_n + 2^n, x_1=1.\)
Solução.Temos
\begin{align*}
x_2 = \amp ~ x_1 + 2\\
x_3 = \amp ~ x_2 + 2^2\\
x_4 = \amp ~ x_3 + 2^3\\
\vdots~~ = \amp ~~~~ \vdots\\
x_n = \amp ~ x_{n-1} + 2^{n-1}.
\end{align*}
Somando, resulta
\begin{align*}
x_n = \amp~ x_1 + (2+2^2+2^3+\cdots+2^{n-1})\\
= \amp~ 1+2+2^2+2^3+\cdots+2^{n-1}\\
= \amp~ 1\frac{2^n-1}{2-1}\\
= \amp~ 2^n-1.
\end{align*}
Exemplo 4.2.7.
Resolva a recorrência \(x_{n+1}=x_n + n, x_1=0.\)
Solução.Temos
\begin{align*}
x_2 = \amp ~ x_1 + 1\\
x_3 = \amp ~ x_2 + 2\\
x_4 = \amp ~ x_3 + 3\\
\vdots~~ = \amp ~~~~ \vdots\\
x_n = \amp ~ x_{n-1} + (n-1).
\end{align*}
Somando, resulta
\begin{align*}
x_n = \amp~ x_1+1+2+3+\cdots+(n-1)\\
= \amp~ 1+2+3+\cdots+(n-1)\\
= \amp~ \frac{n(n-1)}{2}.
\end{align*}
O teorema a seguir mostra que qualquer recorrência linear não-homogênea de primeira ordem pode ser transformada em uma da forma \(x_{n+1}=x_n+f(n)\text{.}\)
Teorema 4.2.8.
Se \(a_n\) é uma solução não nula da recorrência
\begin{equation*}
x_{n+1} = g(n)x_n,
\end{equation*}
então a substituição \(x_n=a_ny_n\) transforma a recorrência
\begin{equation*}
x_{n+1}=g(n)x_n+h(n)
\end{equation*}
em
\begin{equation*}
y_{n+1}=y_n+h(n)(g(n)\cdot a_n)^{-1}.
\end{equation*}
Demonstração.
A substituição \(x_n=a_ny_n\) transforma
\begin{equation*}
x_{n+1}=g(n)x_n+h(n) ~~ \text{ em } ~~ a_{n+1}y_{n+1}=g(n)a_ny_n+h(n).
\end{equation*}
Mas, \(a_{n+1}=g(n)a_n\text{,}\) pois \(a_n\) é solução de \(x_{n+1}=g(n)x_n\text{.}\) Portanto, a equação se transforma em
\begin{equation*}
g(n)a_ny_{n+1} = g(n)a_ny_n+h(n),
\end{equation*}
ou seja, \(y_{n+1}=y_n+h(n)(g(n)\cdot a_n)^{-1}\text{.}\)
Exemplo 4.2.9.
Resolva a recorrência \(x_{n+1}=2x_n + 1, x_1=2.\)
Solução.Uma solução não nula de \(x_{n+1}=2x_n\) é, por exemplo, \(x_n=2^{n-1}\text{,}\) conforme vimos no Exemplo 4.2.4. Fazendo a substituição \(x_n=2^{n-1}y_n\text{,}\) obtemos
\begin{equation*}
2^ny_{n+1}=2^ny_n+1,
\end{equation*}
ou seja,
\begin{equation*}
y_{n+1}=y_n+2^{-n}.
\end{equation*}
Daí, se tem
\begin{align*}
y_2 = \amp ~ y_1 + 2^{-1}\\
y_3 = \amp ~ y_2 + 2^{-2}\\
y_4 = \amp ~ y_3 + 2^{-3}\\
\vdots~~ = \amp ~~~~ \vdots\\
y_n = \amp ~ y_{n-1} + 2^{-(n-1)}.
\end{align*}
Somando, resulta
\begin{align*}
y_n = \amp~ y_1+2^{-1}+2^{-2}+2^{-3}+\cdots+2^{-(n-1)}\\
= \amp~ y_1+2^{-1}\frac{(2^{-1})^{n-1}-1}{2^{-1}-1}\\
= \amp~ y_1-2^{1-n}+1.
\end{align*}
Como \(x_n=2^{n-1}y_n\) e \(x_1=2\text{,}\) temos \(y_1=2\) e \(y_n=3-2^{1-n}\text{.}\) Daí, \(x_n=3\cdot 2^{n-1}-1.\)
Exemplo 4.2.10.
Resolva \(x_{n+1}=3x_n+3^n, x_1=2\text{.}\)
Solução.Uma solução não nula de \(x_{n+1}=3x_n\) é, por exemplo, \(x_n=3^{n-1}\) (ou qualquer outra progressão geométrica de razão 3). Fazendo a substituição \(x_n=3^{n-1}y_n\text{.}\) Obtemos \(3^ny_{n+1}=3^ny_n+3^n\text{,}\) ou seja, \(y_{n+1}=y_n+1\text{.}\) Daí, \(y_n\) é uma progressão aritmética de razão 1. Logo, \(y_n=y_1+(n-1)1\text{.}\) Como \(x_n=3^{n-1}y_n\) e \(x_1=2\text{,}\) temos \(y_1=2\) e \(y_n=n+1\text{.}\) Daí, \(x_n=(n+1)3^{n-1}\text{.}\)
