6: Індукція та рекурсія
- Page ID
- 64864
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Деякі проблеми найпростіше вирішити (або підрахувати) за допомогою рекурсивно визначеної послідовності. Ми почнемо цю главу з введення цих послідовностей.
Ви повинні були бачити основні докази шляхом індукції принаймні в одному попередньому курсі. Докази за допомогою індукції є важливою математичною технікою, і часто використовуються в опублікованих роботах. Ми зробимо швидкий огляд основних доказів шляхом індукції, застосовуючи їх до рекурсивно визначених послідовностей. Тоді ми торкнемося деяких трохи більш складних застосувань індукції. Докази за допомогою індукції будуть технікою, яку ми будемо використовувати протягом решти курсу, в різних контекстах.
- 6.1: Рекурсивно визначені послідовності
- Можливо, ви знайомі з терміном «рекурсія» як техніка програмування. Він походить від того ж кореня, що і слово «повторюватися», і є технікою, яка передбачає багаторазове застосування визначення самопосилання, поки ми не досягнемо деяких початкових термінів, які явно визначені, а потім повертаємося через програми, щоб розробити результат, який ми хочемо. Якщо ви цього не дотримувалися, нічого страшного, ми розглянемо визначення та деякі конкретні приклади, які повинні дати вам ідею.
- 6.2: Основна індукція
- У доказі шляхом індукції визначення того, що P (n0) є істинним для якогось конкретного цілого числа n0, називається базовим випадком. Доведення умовного твердження, що P (k) ⇒P (k+1) для кожного k ≥ n0 називається індуктивним кроком. Припущення, яке ми робимо в індуктивному кроці, що P (k) вірно для деяких довільних k ≥ n0, називається індуктивною гіпотезою і може бути посилатися (IH), коли вона використовується в доказі.
- 6.3: Більш просунута індукція
- Тепер, коли ми розглянули основну форму індукції, важливо розглянути деякі більш просунуті форми, які часто використовуються. Перша форма, яку ми розглянемо, - сильна індукція. Коли ми маємо рекурсивно визначену послідовність, яка залежить від попередніх термінів, іноді нам потрібно знати не тільки про єдиний термін, який приходить безпосередньо перед n-м терміном, а про інші попередні терміни. Тільки склавши всю цю інформацію разом, ми зможемо вивести потрібний нам результат приблизно на n-й термін.
- 6.4: Резюме
- Ця сторінка містить короткий зміст тем, охоплених у розділі 6.