Смекни!
smekni.com

Система натуральных чисел. Принцип математической индукции. Теоремы математической индукции (стр. 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