Exemplo 4.3.1.
A recorrência \(x_{n+2}=x_{n+1}+x_n\) tem equação característica \(r^2=r+1\text{.}\) As raízes da equação característica são:
\begin{equation*}
r_1=\frac{1+\sqrt{5}}{2}~~ \text{ e } ~~ r_2=\frac{1-\sqrt{5}}{2}.
\end{equation*}
Seção 4.3 Recorrências Lineares de Segunda Ordem
Inicialmente, trataremos das recorrências lineares de segunda ordem homogêneas com coeficientes constantes, isto é, recorrências da forma
\begin{equation*}
x_{n+2}+px_{n+1}+qx_n=0.
\end{equation*}
Suporemos sempre \(q\neq 0\text{,}\) pois se \(q=0\text{,}\) a recorrência seria, na realidade, uma recorrência de primeira ordem.
A cada recorrência linear de segunda ordem homogênea, com coeficientes constantes, da forma acima, associaremos uma equação do segundo grau,
\begin{equation*}
r^2+pr+q=0,
\end{equation*}
chamada equação característica. A nossa suposição preliminar de que \(q\neq 0\) implica que \(0\) não é raiz da equação característica.
O teorema a seguir mostra que se as raízes da equação característica são \(r_1\) e \(r_2\text{,}\) com \(r_1\neq r_2\text{,}\) então qualquer sequência da forma \(a_n=C_1r_1^n + C_2r_2^n\) é solução da recorrência, quais que sejam os valores das constantes \(C_1\) e \(C_2\text{.}\)
Teorema 4.3.2.
Se as raízes de \(r^2+pr+q=0\) são \(r_1\) e \(r_2\text{,}\) com \(r_1\neq r_2\text{,}\) então \(a_n=C_1r_1^n + C_2r_2^n\) é solução da recorrência \(x_{n+2}+px_{n+1}+qx_n=0\text{,}\) quaisquer que sejam os valores das constantes \(C_1\) e \(C_2\text{.}\)
Demonstração.
Substituindo \(a_n=C_1r_1^n + C_2r_2^n\) na recorrência \(x_{n+2}+px_{n+1}+qx_n=0\text{,}\) obtemos, agrupando convenientemente os termos,
\begin{equation*}
C_1r_1^n(r_1^2+pr_1+q) + C_2r_2^n(r_2^2+pr_2+q) = C_1r_1^n\cdot 0 + C_2r_2^n\cdot 0=0.
\end{equation*}
Exemplo 4.3.3.
A equação \(x_{n+2}+3x_{n+1}-4x_n=0\) tem \(r^2+3r-4=0\) como equação característica. As raízes da equação são \(1\) e \(-4\text{.}\) De acordo com o Teorema 4.3.2, todas as sequências da forma \(a_n=C_11^n+C_2(-4)^n\) são soluções da recorrência.
Teorema 4.3.4.
Se as raízes de \(r^2+pr+q=0\) são \(r_1\) e \(r_2\text{,}\) com \(r_1\neq r_2\text{,}\) então todas as soluções da recorrência \(x_{n+2}+px_{n+1}+qx_n=0\) são da forma \(a_n=C_1r_1^n+C_2r_2^n, C_1\) e \(C_2\) constantes.
Demonstração.
Seja \(y_n\) uma solução qualquer de \(x_{n+2}+px_{n+1}+qx_n=0\text{.}\) Determinemos constantes \(C_1\) e \(C_2\) que sejam soluções do sistema de equações:
\begin{equation*}
\begin{cases}
C_1r_1+C_2r_2=y_1\\
C_1r_1^2+C_2r_2^2=y_2\\
\end{cases}
\end{equation*}
isto é,
\begin{equation*}
C_1 = \frac{r_2^2y_1-r_2y_2}{r_1r_2(r_2-r_1)}~~ \text{ e } C_2=\frac{r_1y_2-r_1^2y_1}{r_1r_2(r_2-r_1)}.
\end{equation*}
Isso é possível, pois \(r_1\neq r_2\text{,}\) \(r_1\neq 0\) e \(r_2\neq 0\text{.}\)
Afirmamos que \(y_n = C_1r_1^n+C_2r_2^n\) para todo \(n\) natural, o que provará o teorema. Com efeito, seja \(z_n=y_n-C_1r_1^n-C_2r_2^n\text{.}\) Mostraremos que \(z_n=0\) para todo \(n\text{.}\) Temos
\begin{equation*}
z_{n+2}+pz_{n+1}+qz_n=\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
\end{equation*}
\begin{equation*}
\quad\quad=(y_{n+2}+py_{n+1}+qy_n)-C_1r_1^n(r_1^2+pr_1+q)-C_2r_2^n(r_2^2+pr_2+q).
\end{equation*}
O primeiro parênteses é igual a zero porque \(y_n\) é solução de \(x_{n+2}+px_{n+1}+qx_n=0\text{;}\) os dois últimos parênteses são iguais a zero porque \(r_1\) e \(r_2\) são raízes de \(r^2+pr+q=0\text{.}\) Então \(z_{n+2}+pz_{n+1}+qz_n=0\text{.}\) Além disso, como \(C_1r_1+C_2r_2=y_1\) e \(C_2r_1^2+C_2r_2^2=y_2\text{,}\) temos \(z_1=z_2=0\text{.}\) Mas, se \(z_{n+2}+pz_{n+1}+qz_n=0\) e \(z_1=z_2=0\text{,}\) então \(z_n=0\) para todo \(n\text{.}\)
Exemplo 4.3.5.
Determine as soluções da recorrência \(x_{n+2}+3x_{n+1}-4x_n=0.\)
Solução.A equação característica \(r^2+3r-4=0\text{,}\) tem raízes \(1\) e \(-4\text{.}\) De acordo com o Teorema 4.3.2 e o Teorema 4.3.4, as soluções da recorrência são as sequências da forma \(a_n=C_11^n+C_2(-4)^n\text{,}\) isto é, \(a_n=C_1+C_2(-4)^n\text{,}\) na qual, \(C_1\) e \(C_2\) são constantes arbitrárias.
Exemplo 4.3.6.
Determine o número de Fibonacci \(F_n\) definido por
\begin{equation*}
F_{n+2}=F_{n+1}+F_n, \quad\text{ com } \quad F_1=F_2=1.
\end{equation*}
A equação característica é \(r^2=r+1\) e suas raízes são dadas por
\begin{equation*}
r_1 = \frac{1+\sqrt{5}}{2} ~~ \text{ e }~~ r_2 = \frac{1-\sqrt{5}}{2}.
\end{equation*}
Então,
\begin{equation*}
F_n=C_1\left( \frac{1+\sqrt{5}}{2} \right)^n + C_2\left( \frac{1-\sqrt{5}}{2} \right)^n.
\end{equation*}
Para determinar \(C_1\) e \(C_2\text{,}\) podemos usar \(F_1=F_2=1\text{,}\) mas é mais conveniente usar \(F_0=0\) e \(F_1=1\text{.}\)
Obtemos o sistema
\begin{equation*}
\begin{cases}
C_1+C_2=0\\
C_1\left( \frac{1+\sqrt{5}}{2} \right) +C_2\left( \frac{1-\sqrt{5}}{2} \right)=1.\\
\end{cases}
\end{equation*}
Resolvendo o sistema, encontramos \(C_1=-C_2=\frac{1}{\sqrt{5}}\text{.}\) Daí:
\begin{equation*}
F_n=\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^n.
\end{equation*}
Nota 4.3.7.
Se as raízes da equação característica forem complexas, a solução \(a_n = C_1r_1^n + C_2r_2^n,\) \(C_1\) e \(C_2\) constantes arbitrárias pode ser escrita de modo a evitar cálculos com números complexos. Pondo as raízes na forma trigonométrica, teremos:
\begin{equation*}
r_1 = \rho(\cos{\theta}+ i\sin{\theta}), \quad\quad r_2 = \rho(\cos{\theta}- i\sin{\theta})
\end{equation*}
\begin{equation*}
r_1^n = \rho^n(\cos{n\theta}+ i\sin{n\theta}), \quad\quad r_2^n = \rho^n(\cos{n\theta}- i\sin{n\theta}).
\end{equation*}
Logo,
\begin{equation*}
C_1r_1^n+C_2r_2^n = \rho^n((C_1+C_2)\cos{n\theta}+ i(C_1-C_2)\sin{n\theta}).
\end{equation*}
É claro que \(C_1'=C_1+C_2\) e \(C_2'=i(C_1-C_2)\) são novas constantes e a solução pode ser escrita como
\begin{equation*}
a_n = \rho^n(C_1'\cos{n\theta}+C_2'\sin{n\theta}).
\end{equation*}
Exemplo 4.3.8.
A recorrência \(x_{n+2}-x_{n+1}+x_n=0\) tem equação característica \(r^2-r+1=0\text{,}\) cujas raízes são
\begin{equation*}
r_1=\frac{1+i\sqrt{3}}{2} ~~ \text{ e } ~~ r_2 = \frac{1-i\sqrt{3}}{2},
\end{equation*}
que são complexas de módulo \(\rho =1\) e argumento principal \(\theta = \pm\frac{\pi}{3}\text{.}\)
A solução é
\begin{equation*}
x_n = \rho^n(C_1\cos{n\theta}+C_2\sin{n\theta}) = C_1\cos{\frac{n\pi}{3}}+C_2\sin{\frac{n\pi}{3}}.
\end{equation*}
O que acontece se as raízes da equação característica forem iguais? Os teoremas a seguir respondem essa pergunta.
Teorema 4.3.9.
Se as raízes de \(r^2+pr+q=0\) são iguais, \(r_1=r_2=r\text{,}\) então,
\begin{equation*}
a_n=C_1r^n+C_2nr^n
\end{equation*}
é a solução da recorrência
\begin{equation*}
x_{n+2}+px_{n+1}+qx_n=0,
\end{equation*}
quaisquer que sejam os valores das contantes \(C_1\) e \(C_2\text{.}\)
Demonstração.
Se as raízes são iguais, então \(r=-\frac{p}{2}\text{.}\) Substituindo \(a_n=C_1r^n+C_2nr^n\) na recorrência
\begin{equation*}
x_{n+2}+px_{n+1}+qx_n=0
\end{equation*}
obtemos,
\begin{equation*}
C_1r^n(r^2+pr+q)+C_2nr^n(r^2+pr+q) + C_2r^nr(2r+p)
\end{equation*}
\begin{equation*}
= C_1r^n\cdot0+C_2nr^n\cdot0+C_2r^nr\cdot0=0.
\end{equation*}
Teorema 4.3.10.
Se as raízes de \(r^2+pr+q=0\) são iguais, \(r_1=r_2=r\text{,}\) então todas as soluções da recorrência \(x_{n+2}+px_{n+1}+qx_n=0\) são da forma \(C_1r^n+C_2nr^n\text{,}\) \(C_1\) e \(C_2\) constantes.
Demonstração.
Seja \(y_n\) uma solução qualquer de \(x_{n+2}+px_{n+1}+qx_n=0\text{.}\) Determine constantes \(C_1\) e \(C_2\) que sejam soluções do sistema de equações.
\begin{equation*}
\begin{cases}
C_1r+C_2r=y_1\\
C_1r^2+2C_2r^2=y_2
\end{cases}
\end{equation*}
isto é possível, pois \(r\neq 0\text{.}\)
Afirmamos que \(y_n=C_1r^n+C_2nr^n\) para todo \(n\) natural, o que provará o teorema. Com efeito, seja \(z_n=y_n-C_1r^n-C_2nr^n\text{.}\) Mostraremos que \(z_n=0\) para todo \(n\text{.}\) Temos
\begin{equation*}
z_{n+2}+pz_{n+1}+qz_n=(y_{n+2}+py_{n+1}+qy_n)-
\end{equation*}
\begin{equation*}
-C_1r^n(r^2+pr+q)-C_2nr^n(r^2+pr+q)-C_2r^nr(2r+p).
\end{equation*}
O primeiro parênteses é igual a zero porque \(y_n\) é a solução de \(x_{n+2}+px_{n+1}+qx_n=0\text{;}\) o segundo e terceiro parênteses são iguais a zero porque \(r\) é raiz de \(r^2+pr+q=0\text{;}\) o quarto é igual a zero porque \(2r+p=0\) já que, quando \(r_1=r_2=r\text{,}\) tem-se \(r=-\frac{p}{2}\text{.}\) Então, \(z_{n+2}+pz_{n+1}+qz_n=0\text{.}\)
Além disso, como \(C_1r+C_2r=y_1\) e \(C_1r^2+2C_2r^2=y_2\text{,}\) temos \(z_1=z_2=0\text{.}\) Mas, se \(z_{n+2}+pz_{n+1}+qz_n=0\) e \(z_1=z_2=0\text{,}\) então \(z_n=0\) para todo \(n\text{.}\)
Exemplo 4.3.11.
A recorrência \(x_{n+2}-4x_{n+1}+4x_n=0\) tem equação característica \(r^2-4r+4=0\text{.}\) As raízes são \(r_1=r_2=2\) e a solução da recorrência é \(x_n=C_12^n+C_2n2^n\text{.}\)
O teorema a seguir mostra um processo para resolver algumas recorrências não homogêneas.
Teorema 4.3.12.
Se \(a_n\) é uma solução da equação
\begin{equation*}
x_{n+2}+px_{n+1}+qx_n=f(n),
\end{equation*}
então a substituição \(x_n=a_n+y_n\) transforma a equação em
\begin{equation*}
y_{n+2}+py_{n+1}+qy_n=0.
\end{equation*}
Demonstração.
Substituindo \(x_n\) por \(a_n+y_n\) na equação, obtemos
\begin{equation*}
(a_{n+2}+pa_{n+1}+qa_n)+(y_{n+2}+py_{n+1}+qy_n)=f(n).
\end{equation*}
Mas \(a_{n+2}+pa_{n+1}+qa_n=f(n)\text{,}\) pois \(a_n\) é a solução da equação original. Logo, a equação se transformou em
\begin{equation*}
y_{n+2}+py_{n+1}+qy_n=0.
\end{equation*}
De acordo com o Teorema 4.3.12, a solução de uma recorrência não homogênea é constituída de duas parcelas: uma solução qualquer da não homogênea e a solução da homogênea. A solução da homogênea, sabemos achar. Uma solução da não homogênea, procuramos por tentativas.
Exemplo 4.3.13.
Determine a solução da recorrência:
\begin{equation*}
x_{n+2}-6x_{n+1}+8x_n=n+3^n.
\end{equation*}
A recorrência tem equação característica \(r^2-6r+8=0\text{,}\) cujas raízes são \(r_1=2\) e \(r_2=4\text{.}\) Portanto, a solução da homogênea, isto é, de \(x_{n+2}-6x_{n+1}+8x_n=0\) é \(h_n=C_12^n+C_24^n\text{.}\) Tentaremos agora descobrir uma solução particular, \(t_n\text{,}\) da recorrência
\begin{equation*}
x_{n+2}-6x_{n+1}+8x_n=n+3^n.
\end{equation*}
Ora, se substituirmos \(t_n\) em \(x_{n+2}-6x_{n+1}+8x_n\) devemos encontrar \(n+3^n\text{.}\) Que tipo de função deve ter \(t_n\text{?}\) É bastante razoável imaginar que \(t_n\) seja a soma de um polinômio do primeiro grau com uma exponencial de base 3. Tentaremos \(t_n=An+B+C3^n\text{.}\) Substituindo em
\begin{equation*}
x_{n+2}-6x_{n+1}+8x_n=n+3^n,
\end{equation*}
obtemos \(3An+3B-4A-C3^n=n+3^n\text{.}\) Logo, \(t_n\) será solução se \(3A=1, 3B-4A=0\) e \(-C=1\text{.}\) Logo,
\begin{equation*}
A=\frac{1}{3}, B=\frac{4}{9}, \text{ e } C=-1.
\end{equation*}
Daí,
\begin{equation*}
t_n=\frac{1}{3}n+\frac{4}{9}-3^n.
\end{equation*}
Portanto, a solução da recorrência não homogênea é
\begin{equation*}
x_n=C_12^n+C_24^n+\frac{1}{3}n+\frac{4}{9}-3^n.
\end{equation*}
Exemplo 4.3.14.
Determine a solução da recorrência:
\begin{equation*}
x_{n+2}-6x_{n+1}+8x_n=1+2^n.
\end{equation*}
A recorrência tem equação característica \(r^2-6r+8=0\text{,}\) cujas raízes são \(r_1=2\) e \(r_2=4\text{.}\) Portanto, a solução da homogênea, isto é, de \(x_{n+2}-6x_{n+1}+8x_n=0\) é \(h_n=C_12^n+C_24^n\text{.}\) Tentaremos agora descobrir uma solução particular, \(t_n\) da recorrência \(x_{n+2}-6x_{n+1}+8x_n=1+2^n\text{.}\) Ora, se substituirmos \(t_n\) em \(x_{n+2}-6x_{n+1}+8x_n\) devemos encontrar \(1+2^n\text{.}\) Que tipo de função deve ser \(t_n\text{?}\) É bastante razoável imaginar que \(t_n\) seja a soma de um polinômio constante com uma exponencial de base 2. Tentaremos \(t_n=A+B2^n\text{.}\) Substituindo em
\begin{equation*}
x_{n+2}-6x_{n+1}+8x_n=1+2^n,
\end{equation*}
obtemos \(3A=1+2^n\text{.}\) Essa igualdade é impossível. A recorrência não admite solução da forma \(t_n=A+B2^n\text{.}\)
Parando para pensar no que aconteceu, verificamos que era óbvio que a nossa tentativa não podia dar certo. O espírito da nossa tentativa era tentar uma constante \(A\) para que obtivéssemos uma constante que igualaríamos a 1 e tentar \(B2^n\) para gerar uma exponencial que pudéssemos igualar a \(2^n\text{.}\) É claro que o termo \(B2^n\) não poderia cumprir o seu papel. \(B2^n\) é solução da homogênea (é a solução da homogênea que é obtida pondo \(C_1=B\) e \(C_2=0\)) e, substituindo na equação daria zero e não uma exponencial que pudéssemos igualar a \(2^n\text{.}\)
Vamos corrigir a nossa tentativa para \(t_n=A+Bn2^n\text{.}\) Sempre que na nossa tentativa em algum bloco não cumprir o seu papel, fazemos a correção "aumentando o grau", isto é, multiplicando o bloco por \(n\text{.}\) Agora, substituindo na recorrência, obtemos \(3A-4B2^n=1+2^n\text{,}\) ou seja,
\begin{equation*}
A=\frac{1}{3} \quad \text{ e } \quad B=-\frac{1}{4},
\end{equation*}
Assim, obtemos a solução
\begin{equation*}
t_n=\frac{1}{3}-\frac{n2^n}{4}.
\end{equation*}
A solução da recorrência é a soma de \(h_n\) com \(t_n\text{.}\) Portanto,
\begin{equation*}
x_n=C_12^n+C_24^n+\frac{1}{3}-\frac{n2^n}{4}.
\end{equation*}
Podemos verificar as soluções das recorrências usando o software Maxima da seguinite maneira:
Nota 4.3.15.
O Teorema 4.3.12 pode ser utilizado para resolver uma recorrência linear não homogênea de qualquer grau, toda vez que se conheça a solução geral \(y_n\) da recorrência homogênea correspondente e uma solução particular \(a(n)\text{:}\) a solução geral da equação não homogênea é dada por \(x_n=a_n+y_n\text{.}\) Ilustramos este fato resolvendo, de um outro modo, a recorrência linear de primeira ordem vista no Exemplo 4.2.10.
Exemplo 4.3.16.
Resolva a recorrência \(x_{n+1}=3x_n+3^n, x_1=2\text{,}\) usando o método sugerido pelo Teorema 4.3.12.
Solução.A equação homogênea correspondente é \(x_{n+1}=3x_n\text{,}\) cuja solução geral é \(y_n=C3^n\text{.}\) Para encontrar uma solução particular da recorrência, poderia parecer natural buscar uma solução da forma \(a_n=k3^n\text{.}\) Mas, como no exemplo anterior, isto não funciona, pois soluções deste tipo satisfazem a equação homogênea. Buscamos, então, uma solução da forma \(a_n=kn3^n\text{.}\) Substituindo na recorrência, obtemos \(k(n+1)3^{n+1}=3kn3^n+3^n\text{.}\) Daí, obtemos \(3kn+3k=3kn+1\text{,}\) o que leva a \(k=\frac{1}{3}\text{.}\) Logo, a solução geral da recorrência é \(x_n=C3^n+\frac{1}{3}n3^n\text{.}\) Finalmente, usando a condição inicial \(x_1=2\text{,}\) obtemos \(2=3C+1\text{,}\) que fornece \(C=\frac{1}{3}\text{.}\) Logo, a solução da recorrência é
\begin{equation*}
x_n=\frac{1}{3}3^n+\frac{1}{3}n3^n=(n+1)3^{n-1},
\end{equation*}
como encontrado anteriormente.
