Докажите, что произведение n подряд идущих чисел Фиббоначи кратно F1,F2,F3...Fn (цифры это номера чисел фибоначчи)

задан 5 Окт '17 21:57

10|600 символов нужно символов осталось
0

Вроде как $%F_m$% делится на $%F_k$%, если $%m$% делится на $%k$% ...итого, надо показать, что $%(N+1)\cdot\ldots\cdot(N+n)$% делится на $%n!$%... но ведь $$ \frac{(N+1)\cdot\ldots\cdot(N+n)}{n!} = C_{N+n}^n \;\;\text{- целое...} $$ то есть всё выполняется...

ссылка

отвечен 6 Окт '17 3:25

изменен 6 Окт '17 3:25

@all_exist: по-моему, здесь одно из другого сразу не следует. Из того, что произведение делится на n!, мы не можем сделать вывод, что один сомножитель в числителе делится на 1, другой на 2, ... , n-й на n.

(6 Окт '17 12:41) falcao

@falcao, а в чем проблема? Среди n последовательных при $%n>m$% всегда есть кратное m. Пусть это $%F_{km}$%, тогда уже оно делится на $%F_m$%, а на все прочие множители можно не обращать внимания. То бишь вот я совсем не понимаю, при чем тут факториалы и биномиальные коэффициенты.

(6 Окт '17 13:16) knop

@knop: это рассуждение показывает, что на каждое F_m (1<=i<=m) делится некоторое число Фибоначчи из списка n последовательных. Но отсюда прямо не следует, что произведение будет делиться на произведение. Проблема в том, что на разные F_m может делиться одно и то же число. При этом, из делимости на F_i и F_j не следует в общем случае делимость на F_iF_j. Думаю, что идея может быть доработана, но нужна какая-то техника (анализ взаимной простоты и так далее).

(6 Окт '17 14:12) falcao
10|600 символов нужно символов осталось
0

Это утверждение проще всего доказать по индукции. Надо использовать тождество $%F_{m+n}=F_nF_{m-1}+F_{n+1}F_m$%, где $%F_0=0$%, $%F_{-1}=1$%. Здесь нам важно то, что $%F_{m+n}$% можно представить в виде $%uF_m+vF_n$%, где $%u$%, $%v$% целые.

Утверждение о делимости $%F_{m+1}\ldots F_{m+n}$% на $%F_1\ldots F_n$% доказываем индукцией по $%n\ge1$%, а при фиксированном $%n$% по $%m\ge0$%. Случай $%n=1$% очевиден. Пусть $%n > 1$%. База индукции $%m=0$% также очевидна. Пусть $%m\ge1$%; осуществляем шаг от $%m-1$% к $%m$%. В произведении $%F_{m+1}\ldots F_{m+n}$% последний сомножитель раскладываем по $%F_m%$% и $%F_n$%. Получается $%uF_{m+1}\ldots F_{m+n-1}F_m+vF_{m+1}\ldots F_{m+n-1}F_n$%. Первое слагаемое делится на $%F_mF_{m+1}\ldots F_{m+n-1}$%, а потому и на $%F_1\ldots F_n$% по предположению индукции. Далее, $%F_{m+1}\ldots F_{m+n-1}$% делится на $%F_1\ldots F_{n-1}$%, и после домножения на $%F_n$% получается, что второе слагаемое также делится на произведение первых $%n$% чисел Фибоначчи.

ссылка

отвечен 6 Окт '17 16:31

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,495
×1,103
×295
×148
×37

задан
5 Окт '17 21:57

показан
526 раз

обновлен
6 Окт '17 16:31

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru