Система натуральных чисел. Принцип математической индукции. Теоремы математической индукции (стр. 2 из 2)
Для вычисления чисел Фибоначчи справедлива следующая формула Бине
(3)
, 
.Из (1) и (2) следует, что индукционное предположение, при доказательстве формулы Бине, должно предполагать справедливость (3) для
и 
, и значит, начальные условия должны требовать выполнение (3) для 
и 
. Поэтому доказательство формулы Бине может проводиться по следующей теореме математической индукции.Теорема 5. Пусть
- одноместный предикат на 
, который удовлетворяет условиям: 
- истины. 
( 
- истины ® 
- истина).Тогда предикат
тождественно истинен на .Проведём доказательство формулы Бине по теореме 5.
Для
и равенство (3) принимает вид 
, 
.Очевидно, что эти равенства верны.
Предположим, что равенство (3) истинно для чисел
и . Тогда из (2) следует, что 
.После простых преобразований правой части получим, что
По индукции формула Бине доказана.
Теорема 6. Пусть
- одноместный предикат на 
, который удовлетворяет условиям: 
- истина. 
( 
- истины ® 
- истина).Тогда предикат
тождественно истинен на .п.3. Основное свойство ассоциативных операций.
Теорема. Если бинарная операция
на множестве 
ассоциативна, то 
при любой расстановке скобок, задающих порядок выполнения операций в произведении 
значения произведений будут одинаковыми, то есть значение произведения не зависит от способа расстановки скобок.Доказательство. Проводится индукцией по
. Проверим утверждения теоремы для 
и 
.Для
- очевидно, так как порядок выполнения операций единственен.Для
произведение 
может быть вычислено двумя способами: 
или 
. В силу ассоциативности - эти произведения равны.Предположим, что теорема доказана для всех чисел
, где 
.Докажем теорему для числа
. При любой расстановке скобок в произведении 
, такое произведение есть произведение двух скобок 
(1), где 
. Внутри каждой скобки расставлены свои скобки. Так как в каждой скобке множителей, то по индукционному предположению значение произведения в скобках не зависит от того, как в них расставлены скобки. Поэтому произведение (1) можно записать в виде 
, применяя закон ассоциативности и индукцирования к множителям. Получим, что произведение (1) равно 
и так далее продолжая, получим 
, поэтому произведение (1) не зависит от способа расстановки скобок.Список литературы
Е.Е. Маренич, А.С. Маренич. Вводный курс математики. Учебно-методическое пособие. 2002
В.Е. Маренич. Журнал «Аргумент». Задачи по теории групп.
Кострикин А.И. Введение в алгебру. Ч.1 Основы алгебры. – М.: Физмат лит-ра, 2000
Кострикин А.И. Введение в алгебру. Ч.2 Основы алгебры. – М.: Физмат лит-ра, 2000
Кострикин А.И. Введение в алгебру. Ч.3 Основные структуры алгебры. – М.: Физмат лит-ра, 2000
Кострикин А.И. Сборник задач по алгебре. Изд. третье – М.: Физмат лит-ра, 2001