4.2: Детальніше про індукцію

У попередньому розділі ми розглянули доказові заяви бланка\((\forall n \in \mathbb{N}) P(n)\). Математична індукція насправді може бути використана для доведення більш широкої родини результатів; а саме, ті, що мають форму

\((\forall n \in \mathbb{Z})(n \geq a \implies P(n))\)

за будь-яке значення\(a \in \mathbb{Z}\). Теорема 4.2 обробляє особливий випадок, коли\(a = 1\). Аналогія сходів з попередньої секції тримає і для цієї більш загальної ситуації. Щоб довести наступну теорему, імітуйте доказ теореми 4.2, але на цей раз скористайтеся множиною\(S=\{k\in \mathbb{N}\mid P(a+k-1) \text{ is true}\}\).

Теорема 4.9. \(P(a), P(a+1), P(a+2), \ldots\)Дозволяти послідовність операторів, по одному для кожного цілого числа більше або дорівнює\(a\). Припустимо, що

1. \(P(a)\)вірно, і
2. якщо\(P(k)\) істинно, то\(P(k+1)\) істинно.

Тоді\(P(n)\) вірно для всіх цілих чисел\(n \geq a\).

Теорема 4.9 дає процес доведення тверджень виду: «Для всіх цілих чисел\(n\geq a\)»\(P(n)\). Як і раніше, гіпотеза (i) називається базовим кроком, а (ii) називається індуктивним кроком.

Скелет Доказ 4.10. Ось загальна структура доказу шляхом індукції, коли базовий випадок не обов'язково передбачає\(a=1\).

Приступаємо за допомогою індукції.

1. Базовий крок: [Переконайтеся, що\(P(a)\) це правда. Це часто, але не завжди, означає підключення до двох\(n=a\) сторін деякого заявленого рівняння і що обидві сторони насправді рівні.]
2. Індуктивний крок: [Ваша мета - довести: «Для всіх\(k\in\mathbb{Z}\), якщо\(P(k)\) правда, \(P(k+1)\)то істина».] \(k \ge a\)Дозволяти ціле число і припустити, що\(P(k)\) це правда. [Зробіть щось, щоб вивести \(P(k+1)\)це правда.] Тому так\(P(k+1)\) і є.

Таким чином, за індукцією,\(P(n)\) вірно для всіх цілих чисел\(n \ge a\).

Ми зіткнулися з наступною теоремою ще в розділі 3.3 (див. Припущення 3.29), але ми цього не довели. Доводячи цю теорему за допомогою індукції, вам потрібно буде стверджувати, що якщо додати ще один елемент до скінченної множини, то в кінцевому підсумку ви отримаєте вдвічі більше підмножин. Для вашого базового випадку розгляньте порожній набір.

Теорема 4.11. Якщо\(A\) є кінцевим набором з\(n\) елементами, то\(\mathcal{P}(A)\) це набір з\(2^{n}\) елементами.

Теорема 4.12. Для всіх цілих чисел\(n \ge 0\),\(n<2^n\).

Одним з наслідків попередніх двох теорем є те, що множина степенів скінченної множини завжди складається з більшої кількості елементів, ніж початкова множина.

Теорема 4.13. Для всіх цілих\(n \ge 0\) чисел\(4\) ділить\(9^n - 5\).

Теорема 4.14. Для всіх цілих\(n \ge 0\) чисел\(4\) ділить\(6\cdot 7^n - 2 \cdot 3^n\).

Теорема 4.15. Для всіх цілих чисел\(n \ge 2\),\(2^n > n + 1\).

Теорема 4.16. Для всіх цілих чисел\(n \ge 0\),\(1 + 2^1 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\).

Теорема 4.17. Виправте дійсне число\(r \neq 1\). Для всіх цілих чисел\(n \ge 0\)\[\displaystyle{1 + r^1 + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r-1}}.\]

Теорема 4.18. Для всіх цілих чисел\(n \ge 3\),\(\displaystyle{2\cdot 3 + 3 \cdot 4 + \cdots + (n-1)\cdot n = \frac{(n-2)(n^2+2n+3)}{3}}\).

Теорема 4.19. Для всіх цілих чисел\(n \ge 1\),\(\displaystyle{\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}}\).

Теорема 4.20. Для всіх цілих чисел\(n \ge 1\),\(\displaystyle{\frac{1}{1\cdot 3} + \frac{1}{3\cdot 5} + \frac{1}{5\cdot7} + \cdots + \frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1}}\).

Теорема 4.21. Для всіх цілих чисел\(n \ge 0\),\(3^{2n}-1\) ділиться на\(8\).

Теорема 4.22. Для всіх цілих чисел\(n \ge 2\),\(2^n < (n+1)!\).

Теорема 4.23. Для всіх цілих чисел\(n \ge 2\),\(2\cdot 9^n - 10 \cdot 3^n\) ділиться на\(4\).

Ми зараз розглянемо індукційну задачу іншого роду, де доведеться почати з деяких експериментів. Для частини (c) розгляньте можливість використання результатів частин (a) та (b).

Проблема 4.24. Припустимо,\(n\) лінії намальовані в площині так, щоб жодна дві лінії не були паралельними і жодні три лінії не перетиналися в одній точці. Така колекція ліній, як кажуть, знаходиться в загальному положенні. Кожна колекція ліній у загальному положенні ділить площину на нез'єднані області, деякі з яких є багатокутниками з скінченною площею (обмежені області), а деякі з яких не є (необмежені області).

1. \(R(n)\)Дозволяти кількість областей площина розділена на\(n\) лінії в загальному положенні. Згадайте формулу для\(R(n)\) і доведіть, що ваша здогадка вірна.
2. \(U(n)\)Дозволяти кількість необмежених областей площина розділена на\(n\) лінії в загальному положенні. Згадайте формулу для\(U(n)\) і доведіть, що ваша здогадка вірна.
3. \(B(n)\)Дозволяти кількість обмежених областей площина розділена на\(n\) лінії в загальному положенні. Згадайте формулу для\(B(n)\) і доведіть, що ваша здогадка вірна.
4. Припустимо, ми розфарбуємо кожну з областей (обмежену і необмежену) так, щоб жодні дві суміжні області (тобто не мають спільного краю) не мали однакового кольору. Яку найменшу кількість кольорів ми могли б використати для цього? Доведіть своє твердження.