Equações de Diferenças Finitas

Problema da Torre de Hanói

Chamemos a $h_n$ a função que nos diz o número de movimentos necessários para transportar $n$ discos de uma torre para outra.

h_0=0\\ h_n=2h_{n-1}+1

A que se chama uma equação às diferenças finitas. Os coeficientes que multiplicam os termos da sucessão são números — não são dependentes de $n$ . Diz-se então uma equação linear. Nós queremos usar o método das funções geradoras para aprender a resolver equações lineares (escrevemos termos da sucessão à custa de outros termos).

Passos

h_k\quad= 2\qquad h_{k-1}\quad+1\rightarrow \smartcolor{red}{\sum_{k=1}^{+\infty}}h_k\smartcolor{red}{z^k}=2\smartcolor{red}{z\sum_{k=1}^{+\infty}}h_{k-1}\smartcolor{red}{z^{k-1}}+\smartcolor{red}{\sum_{k=1}^{+\infty}z^k}

Note-se que o índice dos somatórios deve ser o menor inteiro para o qual a expressão faz sentido (1, neste caso). Também se deve ter a potência de $z$ coincidente com a ordem da sucessão (valor para $n$ ). Note-se que para o último somatório:

\sum_{k=1}^{+\infty}z^k=\frac{1}{1-z}\smartcolor{red}{-1}=\frac z {1-z}

onde o assinalado a vermelho vem devido ao índice do nosso somatório ( $z^0=1$ ).

Agora, para o somatório do meio:

z\sum_{k=1}^{+\infty}h_{k-1}z^{k-1}=z\sum_{j=0}^{\infty}h_jz^j=zH(z)

onde $H$ é a função geradora de $h_n$ .

logo, finalmente, vem:

h_n=2h_{n-1}+1\quad\Leftrightarrow \quad H_n=2zH_n+\frac{z}{1-z}\\ \longrightarrow H_n=\frac{z}{(1-z)(1-2z)}

Com a fórmula nesta escrita, não conseguimos concluir nada acerca da sucessão $h_n$ . Para isso, decompõe-se as frações com o método de Hermite, ou cover-up method:

\frac{z}{(1-z)(1-2z)}=\frac {\Alpha}{1-z}+ \frac{\Beta}{1-2z}

Para descobrir o coeficiente $\Alpha$ , tapa-se o respetivo denominador na fração inicial e avalia-se a expressão resultante no zero desse denominador, do seguinte modo: