п.1. Аксиоматическая система натуральных чисел.

Определение. Системой натуральных чисел (системой Пеано) называется алгебра , где - бинарные операции, - унарная операция (функция «следования»), - выделенный элемент в множестве , для которой выполнены следующие аксиомы:

Для ,  (элемент  называется следующим за ).

Для , , .

, .

Для , .

, .

Для , .

Аксиома индукции: Пусть . Если множество  удовлетворяет условиям:

а) ;

б) для , ;

то .

Система аксиом Пеано обладает тем свойством, что ни одна из аксиом системы не является следствием других аксиом.

Из системы аксиом Пеано можно вывести все известные нам свойства натуральных чисел.

п.2. Теоремы математической индукции.

Теорема 1. (принцип полной математической индукции). Пусть - одноместный предикат на , который удовлетворяет условиям:

- истина.

 (- истина ® - истина).

Тогда предикат  тождественно истинен на .

Доказательство. Обозначим через  множество всех тех , для которых  истина. Проверим, что  удовлетворяет условиям аксиомы индукции.

Т.к. - истина, то .

Если , то - истина и по второму условию теоремы индукции - истина. Поэтому .

Множество  удовлетворяет условиям аксиомы индукции. Поэтому .

Обозначение. Множество целых чисел  состоит из натуральных чисел, нуля и чисел противоположных натуральным.

Для  обозначим .

Теорема 2. (обобщение принципа полной математической индукции). Пусть - одноместный предикат на , где , который удовлетворяет условиям:

- истина.

 (- истина ®- истина).

Тогда предикат  тождественно истинен на .

Теорема 3. (сильная форма принципа полной математической индукции). Пусть - одноместный предикат на , который удовлетворяет условиям:

- истина.

 (- истины® - истина).

Тогда предикат  тождественно истинен на .

Теорема 4. (обобщение сильной формы принципа полной математической индукции). Пусть - одноместный предикат на , где , который удовлетворяет условиям:

- истина.

 (- истины ® - истина).

Тогда предикат  тождественно истинен на .

Числа Фибоначчи

Определение. Числа Фибоначчи , для , определяются рекуррентно

(1) , ;

 для всех .

Из определения чисел Фибоначчи следует, что

, , , , , , , , , , .

Для вычисления чисел Фибоначчи справедлива следующая формула Бине

(3) , .

Из (1) и (2) следует, что индукционное предположение, при доказательстве формулы Бине, должно предполагать справедливость (3) для  и , и значит, начальные условия должны требовать выполнение (3) для  и . Поэтому доказательство формулы Бине может проводиться по следующей теореме математической индукции.

Теорема 5. Пусть - одноместный предикат на , который удовлетворяет условиям:

- истины.

 (- истины ® - истина).

Тогда предикат  тождественно истинен на .

Проведём доказательство формулы Бине по теореме 5.

Для  и  равенство (3) принимает вид

, .

Очевидно, что эти равенства верны.

Предположим, что равенство (3) истинно для чисел  и . ............