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 =========================================================================
