2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Рекуррентная формула, найти f(n) mod p
Сообщение18.02.2007, 11:59 
Подскажите пажалуста, как решать вот такую задачу:
Дана рекуррентная формула для последовательности $f$:
$f(n)=1+f(1)g(1)+f(2)g(2)+...+f(n-1)g(n-1)$
где $g$ - также повторяющаяся последовательность, данная формулой
$g(n)=1+2g(1)+2g(2)+...+2g(n-1)-g(n-1)g(n-1)$
Известно что $f(1) = 1$, $g(1) = 1$.
Также заданы два числа $n$, $p$
Нужно найти $f(n) \mod p$.
________
Заранее спасибо

 
 
 
 
Сообщение18.02.2007, 13:09 
Это очень просто. Запишем вначале в более компактном виде:
$f(n+1)=f(n)(g(n)+1), \ g(n+1)=g(n-1)^2+3g(n)-g(n)^2.$
По индукции $g(n)=n$, действительно $(n-1)^2+3n-n^2=n+1$. Следовательно $f(n)=n!$

 
 
 
 
Сообщение20.02.2007, 22:11 
Аватара пользователя
 !  Сообщение DneprSerg удалено. Содержательная часть:
DneprSerg писал(а):
Точно, спасибо)

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group