8.3: Інші версії індукції

Іноді важко застосувати Принцип математичної індукції у формі, яку ми виклали в аксіомі\(8.1.2\). Наступна пропозиція містить деякі альтернативні версії, які є більш корисними в деяких з цих ситуацій. Всі вони досить легко випливають з підходу, використовуючи «добре впорядкування», який буде розглянуто в наступному розділі.

Пропозиція\(8.3.1\).

Припустимо,\(P(n)\) це присудок натуральних чисел, і\(m \in \mathbb{N}^{+}\).

1. (Сильна індукція) Якщо
   1. \(​​​​​​P(1)\)правда, і
   2. для кожного\(n \geq 2\),\[((\text { for every } k \in\{1,2, \ldots, n-1\}, P(k)) \Rightarrow P(n)) .\]
      \(P(n)\)то вірно для всіх\(n \in \mathbb{N}^{+}\).
2. (Узагальнена індукція) Якщо
   1. \(P(m)\)правда, і
   2. для кожного\(n > m\)\((P(n-1) \Rightarrow P(n))\),
      то\(P(n)\) вірно для всіх\(n \geq m\).
3. (Сильна індукція з декількома базовими випадками) Якщо
   1. \(P(k)\)вірно для всіх\(k \in\{1,2, \ldots, m\}\), і
   2. для кожного\(n > m\),\[((\text { for every } k \in\{1,2, \ldots, n-1\}, P(k)) \Rightarrow P(n)),\]
      \(P(n)\) то вірно для всіх\(n \in \mathbb{N}^{+}\).
4. Якщо
   1. \(P(1)\)правда, і
   2. для кожного\(k \in \mathbb{N}^{+}\)\(P(k) \Rightarrow P(k+1)\),
      то\(P(n)\) вірно для всіх\(n \in \mathbb{N}^{+}\).
5. Припустимо\(S \subset \mathbb{N}^{+}\). Якщо
   1. \(1 \in S\), і
   2. для кожного\(n \in S\)\((n+1 \in S)\) ,
      тоді\(S = \mathbb{N}^{+}\).

Читати після закінчення Приклад\(8.3.3.\)

Доказ

ШЛЯХОМ ІНДУКЦІЇ.

\(P(n)\)Визначте, щоб бути твердженням\[F_{n}<2^{n}.\]

Ми використовуємо сильну індукцію з 2 базовими корпусами.

1. Базові кейси. У нас є\[F_{1}=1<2=2^{1}\]
   і\[F_{2}=1<4=2^{2},\]
   так\(P(1)\) і\(P(2)\) є правдою.
2. Індукційний крок. Припустимо\(n \geq 3\), і що\(P(n − 1)\) і\(P(n − 2)\) є правдою. Ми маємо\ [\ почати {вирівняний}
   F_ {n} &=F_ {n-1} +F_ {n-2}\\
   &<2^ {n-1} +2^ {n-2}\\
   &<2^ {n-1} +2^ {n-1}\
   &=2^ {n}
   \ кінець {вирівняний}\]
   (Індукційні гіпотези)
   так\(P(n)\) і правда.

За принципом математичної індукції (у вигляді сильної індукції з декількома базовими випадками) робимо висновок,\(P(n)\) що вірно для всіх\(n \in \mathbb{N}^{+}\).

Зауваження\(8.3.2\).

Існує безліч інших варіантів індукції. Наприклад, якщо ви хочете довести, що\(P(n)\) вірно для всіх\(n \in \mathbb{N}\) (а не тільки для всіх\(n \in \mathbb{N}^{+}\)), то

1. ваш базовий випадок буде довести\(P(0)\), і
2. ваш індукційний крок буде довести\(P(n-1) \Rightarrow P(n)\), для всіх\(n \geq 1\).

Приклад\(8.3.3\).

Доведіть\(F_{n} < 2^{n}\), для кожного\(n \in \mathbb{N}^{+}\).