Метод математичної індукції
Метод математичної індукції
При вирішенні математичних задач іноді виникає необхідність довести, що деякий властивість поширюється на всі безліч натуральних чисел (властивість виконується для довільного числа n). Перевірити властивість для кожного числа ми не можемо, оскільки їх кількість нескінченно. Доводиться думати в такий спосіб:
1. Я можу перевірити, чи виконується властивість для n = 1.
2. Я можу показати, що властивість виконується для кожного наступного значення n. А значить властивість буде виконуватися для кожного наступного числа, починаючи з першого.
Такий спосіб докази математичних тверджень називається методом математичної індукції. Він є універсальним методом доведення тверджень, в яких є слова "для довільного натурального n". Доказ методом математичної індукції виробляємо за наступним принципом:
1. База індукції - перевіряємо, що рівність виконується для першого елемента.
2. Індуктивний перехід - доводимо, що якщо властивість виконується для деякого елемента n = k, то воно виконується і для наступного елемента k + 1.
Таким чином, починаючи з першого елемента, ми за допомогою доведеного індуктивного переходу отримуємо справедливість твердження для другого, третього, четвертого. і т.д. тобто для будь-якого натурального n.
На практиці доцільно користуватися наступним алгоритмом:
1. Перевіряємо виконання властивості для першого елемента. (Не обов'язково n1 = 1)
2. Припускаємо, що твердження справедливе для n = k.
3. Доводимо справедливість твердження для n = k + 1.