f(n, p) = (p-2) f(n-1, p) + (p-1) f(n-2, p) para n >= 4.
Ok, agora s� faltava matar o problema definitivamente com uma f�rmula fechada. Estava relendo sobre o maquin�rio de fun��es geradoras e vi que d� pra atacar este problema com fun��es geradoras exponenciais. A minha refer�ncia � o livro do Herbert Wilf, generatingfunctionology (pode baix�-lo gratuitamente na internet).
N�o vou introduzir os conceitos te�ricos, mas a id�ia � fixar o par�metro p e olhar para a fun��o geradora exp.
F = soma_{n >= 0} f(n+4, p) x^n / n!
Uma simples regra mostra a partir da recorr�ncia determinada, ie, f(n+2, p) = (p-2) f(n+1, p) + (p-1) f(n, p), temos
F'' = (p-2) F' + (p-1) F.
Resolvendo a eq. diferencial acima, obtemos F = c_1 exp{-x} + c_2 exp{(p-1)x}, onde c_1 e c_2 s�o constantes que n�o dependem de n (mas podem depender de p).
Tomando a s�rie que representa o lado direito, vemos que
F = soma_{n >= 0} [c_1 (-1)^n + c_2 (p-1)^n] x^n / n!
donde segue que
f(n+4, p) = c_1 (-1)^n + c_2 (p-1)^n.
Verifiquei empiricamente que f(n, p) = (p-1)(-1)^n + (p-1)^n. (para n >= 2)
Para completar uma demonstra��o formal, basta verificar que para n = 2, temos
f(2, p) = p(p-1) = (p-1)(-1)^2 + (p-1)^2 e que para n = 3
f(3, p) = p(p-1)(p-2) = (p-1)(-1)^3 + (p-1)^3
e o resultado segue por indu��o pois o lado direito satisfaz a eq. de recorr�ncia para n > 3.
Simplesmente lindo, n�o �?
Abra�os. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
