FATOS MATEMÁTICOS: A TDL e Aplicações nas Equações de Recorrência

domingo, 10 de junho de 2012

A TDL e Aplicações nas Equações de Recorrência

As equações de recorrência aparecem em várias situações em que as variáveis presentes são medidas por grandezas discretas. Podemos citar o cálculo do montante de capital a juros constantes após $[;n;]$ meses, o cálculo de uma expressão fechada envolvendo o número de movimentos mínimos para resolver a torre de Hanói, o problema da reprodução dos coelhos de Fibonacci e os números de Pell-Lucas.

Tais equações são resolvidas por vários métodos, tais como, a anti-derivada finita ou cálculo natural, a técnica de variação das constantes, substituições adequadas, etc.
Uma técnica eficaz e pouco explorada para resolver as equações de recorrência lineares são as transformadas discretas de Laplace (TDL). A vantagem deste método é a mesma das transformadas de Laplace sobre os métodos tradicionais, isto é, as equações são transformadas em equações algébricas e as condições iniciais do problema são de fato substituição na etapa inicial de resolução. Como a TDL é um assunto recente, vejamos alguns conceitos e proposições que serão úteis em nossa tarefa de resolver as equações de recorrência apresentadas neste post.

Definição 1: A transformada discreta direta de Laplace (TDDL) denotada por $[;\ell_d;]$ da sequência $[;x_n;]$ é definida por

$[;\ell_d\{x_n\} = \sum_{n=0}^{\infty}e^{-sn}x_n = X(s);]$

desde que essa série seja convergente.

Nem todas as sequências admitem a transformada discreta de Laplace, podemos citar, por exemplo $[;x_n = n!;]$ . Deste modo, devemos impor condições sobre a sequência $[;(x_n);]$ de modo que a série acima seja convergente. As sequências $[;(x_n);]$ para os quais a transformada discreta de Laplace existe são chamadas de sequências admissíveis.

É fácil ver que a TDDL é linear e que os ítens da proposição abaixo são facilmente demonstrados usando a definição acima. Além disso, tais provas serão omitidas para não compremeter a dinâmica e os objetivos deste post.

Proposição 1: Se $[;\ell_d;]$ denota a transformada discreta de Laplace, então

$[;i);]$ $[;\ell_d\{1\} = \frac{e^s}{e^s - 1}, \qquad s \succ 0;]$
$[;ii);]$ $[;\ell_d\{n\} = \frac{e^s}{(e^s - 1)^2}, \quad s \succ 0;]$
$[;iii);]$ $[;\ell_d\{r^n\} = \frac{e^s}{(e^s - r)}, \quad e^s \succ r;]$
$[;iv);]$ $[;\ell_d\{x_{n+1}\} = e^sX(s) - x_0;]$
$[;v);]$ $[;\ell_d\{x_{n+2}\} = e^{2s}X(s) - e^{2s}x_0 - e^{s}x_1;]$

Proposição 2: Seja $[;{n \choose p};]$ o coeficiente binomial. Então

$[;\ell_d\bigl\{{n \choose p}\bigr\} = \frac{e^s}{(e^s - 1)^{p+1}}, \quad p \in \mathbb{N};]$

Demonstração: Seja $[;f(x) = 1/(1 - x);]$ definida para $[;x \in (-1,1);]$ . Então para todo $[;n \in \mathbb{N};]$ ,

$[;f^{(p)}(x) = \frac{p!}{(1 - x)^{p+1}} \qquad (1);]$

Para $[;p = 0;]$ é claro que $[;f^{(0)}(x) = 1/(1 - x);]$ . Suponhamos que a expressão $[;(1);]$ seja válida e provaremos que ela também é válida para $[;p + 1;]$ . De fato,

$[;f^{(p+1)}(x) = [f^{(p)}(x)]^{\prime} = p![(1 - x)^{-p-1}]^{\prime};]$

$[;= -(p+1)p!(1 - x)^{-p - 2}(-1) = \frac{(p+1)!}{(1 - x)^{p+2}};]$

Por outro lado, mostraremos que

$[;f^{(p)}(x) = \sum_{n = p}^{\infty}p!{n \choose p}x^{n - p} \qquad (2);]$

Usaremos indução finita sobre $[;p;]$ para provar este resultado. Para $[;p = 0;]$ , temos:

$[;f^{(0)}(x) = \sum_{n = 0}^{\infty}0!{n \choose 0}x^{n - 0} = \sum_{n = 0}^{\infty}x^n = f(x);]$

Suponhamos que a expressão $[;(2);]$ seja válida e provaremos sua validade para $[;p+1;]$ . De fato,

$[;f^{(p + 1)}(x) = [f^{(p)}(x)]^{\prime} = \biggl[\sum_{n = p}^{\infty}p!{n \choose p}x^{n - p}\biggr]^{\prime};]$

$[;= \sum_{n = p + 1}^{\infty}p!(n - p){n \choose p}x^{n-1-p};]$

$[;= \sum_{n = p+1}^{\infty}(p+1)!{n \choose p+1}x^{n - (p+1)};]$

Na última linha, usamos o fato que

$[;p!(n - p){n \choose p} = \frac{p!(n - p)n!}{p!(n - p)!} = \frac{n!}{(n - 1 - p)!} = (p + 1)!{n \choose p+1};]$

Das expressões $[;(1);]$ e $[;(2);]$ , segue que

$[;\sum_{n = p}^{\infty}{n \choose p}x^{n} = \frac{x^p}{(1 - x)^{p+1}};]$

para $[;|x| \prec 1;]$ . Fazendo $[;x = e^{-s};]$ nesta expressão, temos

$[;\sum_{n = p}^{\infty}e^{-sn}{n \choose p} = \frac{(e^{-s})^{p}}{(1 - e^{-s})^{p + 1}} = \frac{e^s}{(e^s - 1)^{p+1}} \qquad (3);]$

Por outro lado,

$[;\ell_d\biggl\{{n \choose p}\biggr\} = \sum_{n = 0}^{\infty}e^{-sn}{n \choose p} = \sum_{n = p}^{\infty}e^{-sn}{n \choose p} \qquad (4);]$

De $[;(3);]$ e $[;(4);]$ segue o resultado.

Definição 2: Se $[;X(s);]$ é a transformada discreta de Laplace de $[;(x_n);]$ , a transformada discreta inversa de Laplace (TDIL) é definida por:

$[;\ell_{d}^{-1}\{X(s)\} = x(n) = x_n;]$

Note que se $[;\mathcal{N}(n) \equiv 0;]$ , então

$[;\ell_d\{x_n + \mathcal{N}_n\} = \ell_d\{x_n\} = X(s) \quad \Rightarrow \ell_{d}^{-1}\{X(s)\} = x_n + \mathcal{N}_n;]$

Deste modo, iremos excluir as sequências nulas para garantir a unicidade da TDIL. Segue da Prop. 1 que:
$[;i);]$ $[;\ell_{d}^{-1}\bigl\{\frac{e^s}{e^s - 1}\bigr\} = 1;]$
$[;ii);]$ $[;\ell_{d}^{-1}\bigl\{\frac{e^s}{e^s - r}\bigr\} = r^n;]$
$[;iii);]$ $[;\ell_{d}^{-1}\biggl\{\frac{e^s}{(e^s - 1)^{p+1}}\biggr\} = {n \choose p};]$
Definição 3: Seja $[;p \in \mathbb{N};]$ . A sequência delta de $[;p;]$ , denotada por $[;\delta_p(n);]$ é definida por:

$[;\delta_p(n) = \begin{cases}1, \quad \text{se} \quad n = p\\0, \quad \text{se} \quad n \neq p\\\end{cases};]$

Proposição 3: Se $[;\delta_p(n);]$ é a sequência delta, então $[;\ell_{d}^{-1}\delta_p(n) = e^{-sp};]$ .
Proposição 4: Se $[;\delta_0(n);]$ a sequência delta de ordem zero, então

$[;\ell_{d}^{-1}\biggl\{\frac{1}{e^s - r}\biggr\} = r^{n- 1} - \frac{\delta_0(n)}{r};]$

Definição 4: Dadas as sequências $[;(x_n);]$ e $[;(y_n);]$ , a convolução denotada por $[;x_n\ast y_n;]$ é definida por

$[;x_n\ast y_n = \sum_{k=0}^{n}x_{n-k}y_{k};]$

É fácil provar que a convolução é comutativa. Uma propriedade importante sobre a convolução é dada na proposição abaixo.

Proposição 5: Se $[;\ell_d\{x_n\} = X(s);]$ e $[;\ell_d\{y_n\} = Y(s);]$ , então

$[;\ell_d\{x_n\ast y_n\} = X(s)Y(s);]$

Vejamos agora algumas aplicações da TDL às equações de recorrência. Um material completo e detalhado está sendo confeccionado.

Problema 1: Considere a sequência de estruturas triangulares conforme a figura abaixo. Quantos segmentos são usados para construir a enésima estrutura?

Observação: Este problema foi baseado em uma questão da primeira fase OBMEP 2012.
Resolução: Seja $[;x_n;]$ a quantidade de segmentos de reta necessário para construir o enésima estrutura. Note que $[;x_1 = 3;]$ , $[;x_2 = a_1 + 3\cdot 2;]$ , $[;a_3 = a_2 + 3\cdot 3;]$ . Por indução finita, pode-se provar que

$[;\begin{cases}x_{n+1} = x_n + 3(n + 1), \quad n \geq 1\\x_1 = 3\\\end{cases};]$

Aplicando a TDL em ambos os lados desta equação, temos:

$[;e^sX(s) - e^sx_0 = X(s) + \frac{3e^s}{(e^s - 1)^2} + \frac{3e^s}{e^s - 1} \quad \Rightarrow;]$

$[;X(s) = x_0\cdot \frac{e^s}{e^s - 1} + \frac{3e^s}{(e^s - 1)^3} + \frac{3e^s}{(e^s - 1)^2};]$

Aplicando a transformada discreta inversa de Laplace nesta expressão, segue que

$[;x_n = x_0\ell_{d}^{-1}\biggl\{\frac{e^s}{e^s - 1}\biggr\} + 3\ell_{d}^{-1}\biggl\{\frac{e^s}{(e^s - 1)^3}\biggr\} + 3\ell_{d}^{-1}\biggl\{\frac{e^s}{(e^s - 1)^2}\biggr\};]$

ou seja,

$[;x_n = x_0 + 3{n \choose 2} + 3{n \choose 1};]$

Sendo $[;x_1 = 3;]$ , então

$[;3 = x_1 = x_0 + 3{1 \choose 2} + 3{1 \choose 1} = x_0 + 3 \quad \Rightarrow \quad a_0 = 0;]$

Logo,

$[;x_n = \frac{3n(n-1)}{2} + 3n = \frac{3}{2}n(n+1);]$

Problema 2: No post, A Torre de Hanói foi deduzido que a quantidade mínima de movimentos para transferir $[;n;]$ discos do pino $[;1;]$ para o pino $[;3;]$ satisfaz a relação de recorrência:

$[;\begin{cases}t_{n+1} = 2t_n + 1, \quad n \geq 1\\t_1 = 1\end{cases};]$

Use a TDL e mostre que $[;t_n = 2^n - 1;]$ .
Resolução: Aplicando a TDL, temos:

$[;\ell_d\{t_{n+1}\} = 2\ell_d\{t_n\} + \ell_d\{1\} \quad \Rightarrow;]$

$[;e^sT(s) - e^st_0 = 2T(s) + \frac{e^s}{e^s - 1};]$

de modo que

$[;T(s) = t_0\frac{e^s}{e^s - 2} + \frac{e^s}{(e^s - 1)(e^s - 2)} \quad \Rightarrow;]$ $[;t_n = t_0\cdot \ell_{d}^{-1}\biggl\{\frac{e^s}{e^s - 2}\biggr\} + \ell_{d}^{-1}\biggl\{\frac{e^s}{(e^s - 1)(e^s - 2)}\biggr\} = t_0 2^n + f(n);]$

onde

$[;f(n) = \ell_{d}^{-1}\biggl\{\frac{e^s}{(e^s - 1)(e^s - 2)} \biggr\};]$

Para calcular esta transformada discreta inversa de Laplace, usamos frações parciais, isto é,

$[;\frac{e^s}{(e^s - 1)(e^s - 2)} = \frac{A}{e^s - 1} + \frac{B}{e^s - 2};]$

de modo que $[;A = -1;]$ e $[;B = 2;]$ . Substituindo estes valores e usando a Prop. 4, temos:

$[;f(n) = \ell_{d}^{-1}\biggl\{\frac{e^s}{(e^s - 1)(e^s - 2)} \biggr\} =;]$
$[;= -1\biggl(1 - \delta_{0}(n)\biggr) + 2\biggl(2^{n-1} - \frac{\delta_0(n)}{2}\biggr) = -1 + 2^n;]$

Assim,

$[;t_n = t_02^n + 2^n - 1;]$

Sendo $[;t_1 = 1;]$ , então $[;1 = t_1 = 2t_0 + 1;]$ , ou seja, $[;t_0 = 0;]$ , donde segue o resultado.
Problema 3: Deposita-se todo mês $[;P;]$ reais em uma conta bancária com rendimento de $[;j;]$ % ao mês. Determine o montante $[;C_n;]$ no enésimo mês.

Resolução: No primeiro mês (mês zero) temos $[;P;]$ reais. No segundo mês (mês 1), temos $[;C_1 = P + P(1 + j);]$ , onde a primeira parcela é o depósito mensal de $[;P;]$ reais e a segunda parcela é o montante (referente + juros) referente ao primeiro mês. Por indução finita, obtemos o PVI:

$[;\begin{cases}C_{n+1} = P + (1 + j)C_n, \quad n \in \mathbb{N}\\C(0) = P\\\end{cases};]$

Aplicando a transformada discreta de Laplace, temos

$[;e^sc(s) - e^sC(0) = \frac{Pe^s}{e^s - 1} + (1 + j)c(s) \quad \Rightarrow;]$

$[;(e^s - 1 - j)c(s) = Pe^s + P\frac{e^s}{e^s - 1} = P\cdot \frac{e^{2s}}{e^s - 1} \quad \Rightarrow;]$

$[;c(s) = P\frac{e^s}{e^s - 1 - j}\cdot \frac{e^s}{e^s - 1};]$

de modo que

$[;C_n = P(1 + j)^n\ast 1 = P\sum_{k = 0}^{n}(1 + j)^k = P\cdot \frac{(1 + j)^{n+1} - 1}{1 + j - 1};]$

ou seja,

$[;C_n = \frac{P}{j}[(1 + j)^{n+1} - 1];]$

Gostará de ler também:

- Um Convite às Transformadas Discretas de Laplace;
- Os Coelhos de Fibonacci e a Sequência de Pell;
- Sequências Aproximantes Para Raízes Quadradas;
- EDO's e Juros Continuamente Compostos;
- A Torre de Hanói.

5 comentários:

Aloisio Teixeira10 de junho de 2012 21:20
Oi, Prof!

Bem sacado a prova da [;TDL;] do coeficiente binomial.

Gostei muito das aplicações também.

Uma vez coloquei no face sobre o escritor com mais livros publicados ( conforme o Guinnes ) que por sinal, é brasileiro.

E sem querer me lembrei do Sr. como sendo o mais prolífero blogueiro de matemática que conheço.

E agora, produzindo matemática original, além da tradicional, sem dúvidas, conforme me falou uma vez, se espelha em Euler.

Um abraço!
ResponderExcluir
Prof. Paulo Sérgio10 de junho de 2012 21:54
Olá Aloísio, também não sei se sou o mais prolífero blogueiro, mas fico muito feliz com suas palavras.

Tenho muito que publicar e acredito que sem dúvidas a internet é maior invenção de todos os tempos, pois através dela podemos expor nossas ideias a várias pessoas além de trocar conhecimentos com pessoas que estão estudando os mesmos assuntos.

Realmente este post é bem original, mas tenho muito que lhe agradecer pela definição de transformada discreta de Laplace, o qual foi o pontapé inicial.
Em breve apresentarei um post aplicando a TDL no cálculo de somatórios.

Obrigado pelos comentários e volte sempre!
ResponderExcluir
Aloisio Teixeira30 de janeiro de 2013 20:38
Paulo, a minha demonstração da função gama discreta deixaria meu próximo artigo muito curto.

Com sua permissão, gostaria de colocar aqui nos comentários usando sua TDL para o binômio [;n \choose p;].

Mas fiquei com uma dúvida. O que significa [;0 \choose p;]?

Até mais.
ResponderExcluir
Respostas

Adicionar comentário

Carregar mais...

Páginas

Membros

domingo, 10 de junho de 2012

A TDL e Aplicações nas Equações de Recorrência

5 comentários: