Математична індукція
( "n:k£n1)[( "m1. Зробити це можна так.
Перевіряється справедливість для всіх простих чиселp.
Доводиться, що й для деякого натуральногоm>1 твердження Â виконано, це твердження виконано і всіх чисел видуm × p, деpпросте.
Звідси теорема про однозначність розкладання натуральних чисел, великих одиниці, на прості співмножники випливає, що твердження Â виконано всімn>1.
Віялова індукція. Під нею розуміється наступний різновид індуктивних доказів.
Нехай потрібно довести справедливість деякого затвердження для всіх натуральнихn³k(k- натуральне). Зробити це можна так.
Перевіряється справедливість для всіх натуральних чисел діапазону [k,k2 - 1].
Доводиться, що якщо для деякого натурального твердження Â виконано, то воно виконане для всіх значенняn × k+r(r= 0,1, ...,k -1).
Звідси випливає, що твердження Â виконане для всіх n >k. Цей факт доводиться методом простої індукції. І зробити це можна, наприклад, так. Проведемо індукцію поs, встановлюючи справедливість для натуральних чиселnвиду:k s -1 £ns - 1 (s=2,3, ...). Приs=2 це те, що випливає з базису зовнішньої індукції. Нехай при деякому натуральномуp ³ sзатвердження Â виконано для значеньnз діапазону:k p- 1 £np - 1. Тоді із індуктивного кроку зовнішньої індукції випливає справедливість для всіхn × k+r(0 £rp £np +1 - 1. Отже, виконано для будь-якихnвиду:k s-1 £ns - 1 при всіхs=2,3,… . Це означає справедливість для всіхn³k.
Тепер кілька слів про рекурсивну сутність дедуктивного методу повної математичної індукції, а точніше його опори - п'ятої аксіоми Пеано. Зупинимося спочатку першому варіанті простий індукції (див. табл. 1).
Проста індукція(перший варіант). Нехай твердженняP(n) потрібно довести для кожного натуральногоnі, тим чи іншим способом, вдалося встановити справедливість тверджень:P( 1) (базис індукції) і ( "n)[P(n) ®P(n+1)] (індукційний крок) Далі на підставі 5-ої аксіоми Пеано в аксіоматиці арифметики робимо висновок про справедливістьP(n) для будь-якого натуральногоn.У чому ж суть цієї аксіоми і де тут рекурсія?Дело все в тому, що якщо базис індукціїP(1) вважати базою рекурсії, то індукційний крок "викреслює" однозначну траєкторію переходів (стверджувань про справедливість) відP(1) до всякогоP(n) при фіксованому значенніn:P(1) ®P(2) ® … ®P(n) Але така жорстка траєкторія переходів однозначно визначає послідовність зворотних посилань відP(n) при фіксованомуnдоP(1):P(n) ÞP(n -1) Þ … ÞP(1) А на це співвідношення ми можемо дивитися як на послідовне зведення завдання обчислення (докази справедливості)P(k) для обчисленняP(k -1) для значеньk:k=n,n -1,…,2, тобто доки потрапимо у основу рекурсіїP(1), одночасно є і базисом індукції. А далі на вихідну послідовність переходівP(1) ®P(2) ® … ®P(n) можна дивитися як на проведення серії відкладених обчисленьаж до отриманняP(n), тобто вирішення вихідної задачі для будь-якого фіксованогоn.
Тим самим нам вдалося встановити рекурсивну природу п'ятої аксіоми Пеано і, отже, першого варіанта методу повної математичної індукції (простий), що базується на ньому. Що ж до інших типів індукції, їх рекурсивна природа так само прозора, як і щойно наведеного. Розглянемо, наприклад, індукцію спуску.
Індукція спуску .Нехай затвердженняP(n) потрібно довести для кожного натуральногоnзадовольняє умовам:k£n£m(kіm- натуральні) і, тим чи іншим способом, вдалося встановити справедливість тверджень:P(m) (базис індукції) і ( "n:kn £m)[P(n) ®P(n -1)] (індукційний крок) Будемо вважати базис індукціїP(m) вважати базою рекурсії.Індукційний крок "викреслює" однозначну траєкторію переходів (тверджень про справедливість) відP(m) до всякогоP( 1):P(m) ®P(m -1) ® … ®P(1 ) Але така жорстка траєкторія переходів однозначно визначає послідовність зворотних посилань відP(1) доP(m):P(1 ) ÞP(2) Þ … ÞP(m) А на це співвідношення ми можемо дивитися як на послідовне зведення завдання обчислення (докази справедливості)P(k -1) до обчисленняP(k) для значеньk:k=2, 3,…,m, тобто поки не потрапимо в основу рекурсіїP(m). А далі на вихідну послідовність переходівP(m) ®P(m -1) ® … ®P(1) можна дивитися як проведення серії відкладених обчислень до отриманняP(1), тобтовирішення вихідного завдання.
Які можна зробити висновки з проведених міркувань? Вони такі. По-перше, кожен тип індукції визначає певний рекурсивний процес, тобто фактично задає конкретну стандартну форму рекурсивних обчислень. По-друге, підстави арифметики, отже, і всієї математики, базуються на рекурсії. Отже, рекурсія може бути методологічною основою та інформатики і, зокрема, навчання алгоритмізації.
Щодо другої іпостасі методу математичної індукції – служити інструментом доказу правильності рекурсивних алгоритмів – зараз нічого спільного ми не говоритимемо. Вона буде продемонстрована пізніше на конкретному задачному матеріалі, що системно пронизує це дослідження.
На закінчення цього розділу зауважимо, що застосування індукції в рекурсії часто спирається на поняття частково впорядкованої множини.