Skip to main content
LibreTexts - Ukrayinska

8.1: Принцип математичної індукції

  1. Last updated
  2. Save as PDF
  • Page ID
    65285

    • \( \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}}\)

    Нагадування\(8.1.1\).

    Сказати, що\(P(n)\) це присудок натуральних чисел, означає, що для кожного натурального числа\(n\), у нас є твердження,\(P(n)\) яке є істинним або хибним. Деякі приклади предикатів:

    • \(P_{odd}(n)\)Дозволяти твердження «\(n\)непарно».
    • Дозвольте\(P_{big}(n)\) бути твердженням «»\(n > 1000\).
    • Дозвольте\(P_{square}(n)\) бути твердженням «»\(\exists k \in \mathbb{N},\left(n=k^{2}\right)\).
    • \(P_{prime}(n)\)Дозволяти твердження «\(n\)це просте число».

    Математики приймають істинність наступного твердження як основний факт про натуральні числа:

    Аксіома\(8.1.2\). (Principle of Mathematical Induction).

    Припустимо,\(P(n)\) це присудок натуральних чисел. Якщо

    1. \(P(1)\)вірно, і
    2. для кожного\(k \geq 2\), (\(P(k-1) \Rightarrow P(k)\)),
      \(P(n)\)то вірно для всіх\(n \in \mathbb{N}^{+}\).

    Хоча ми не можемо довести аксіому\(8.1.2\), це може бути дано неофіційне обгрунтування, яке може переконати вас прийняти її як дійсну властивість\(\mathbb{N}\):

    Доказ

    НЕФОРМАЛЬНЕ ОБГРУНТУВАННЯ.

    \(n\)Дозволяти бути довільним елементом\(\mathbb{N}^{+}\).

    • З (i), ми знаємо, що\(P(1)\) це правда.
    • З (ii), ми знаємо, що\(P(2-1) \Rightarrow P(2)\) це правда.
      Оскільки\(P(2-1)=P(1)\) це правда, робимо висновок, по\(\Rightarrow\) -ліквідації, що\(P(2)\) це правда.
    • З (ii), ми знаємо, що\(P(3-1) \Rightarrow P(3)\) це правда.
      Оскільки\(P(3 − 1) = P(2)\) це правда, робимо висновок, по\(\Rightarrow\) -ліквідації, що\(P(3)\) це правда.
      .
      .
      .
    • З (ii), ми знаємо, що\(P(n − 1) \Rightarrow P(n)\) це правда.
      Оскільки\(P(n − 1)\) це правда, робимо висновок, по\(\Rightarrow\) -ліквідації, що\(P(n)\) це правда. Оскільки\(n\) є довільним елементом\(\mathbb{N}^{+}\), зробимо висновок,\(P(n)\) що вірно для всіх\(n \in \mathbb{N}^{+}\).

    Термінологія\(8.1.3\).

    • У доказі з використанням математичної індукції встановлення (i) називається базовим випадком, а встановлення (ii) є етапом індукції.
    • На етапі індукції ми доказуємо\(P(k − 1) \Rightarrow P(k)\), тому припускаємо, що\(P(k − 1)\) це правда (і встановлюємо\(P(k)\)). Це припущення\(P(k−1)\) називається індукційної гіпотезою.

    Ось приклад того, як може бути використана математична індукція.

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

    Для кожного\(n \in \mathbb{N}^{+}\), у нас є\(1+2+3+\cdots+n=\frac{n(n+1)}{2}\).

    Доказ

    ДОКАЗ ІНДУКЦІЄЮ.

    \(P(n)\)Визначте, щоб бути твердженням\[1+2+3+\cdots+n=\frac{n(n+1)}{2} .\]

    1. Базовий кейс. Бо\(n = 1\), ми маємо\[1+2+3+\cdots+n=1 \quad \text { and } \quad \frac{n(n+1)}{2}=\frac{1(1+1)}{2}=1 .\]
      Оскільки вони рівні,\(P(1)\) це правда.
    2. Індукційний крок. Припустімо\(P(k − 1)\), що це правда (і\(k \geq 2\)). Це означає, що\[1+2+3+\cdots+(k-1)=\frac{(k-1)((k-1)+1)}{2} .\]
      звідси\ [\ почати {вирівняний}
      1+2 &+3+\ cdots+k\\
      & =( 1+2+3+\ cdots+ (k-1)) +k\\
      &=\ frac {(k-1) ((k-1) +1)} {2} +k\\
      &=\ frac {(k-1) k\\
      & amp; = k\ left (\ frac {k-1} {2} +1\ праворуч)\\
      &= k\ ліворуч (\ frac {k+1} {2}\ праворуч)\\\
      &=\ frac {k (k+1)} {2},
      \ end {вирівняний}\]
      (Третя лінія: Індукційна гіпотеза)
      так\(P(k)\) вірно.

    Тому за принципом математичної індукції ми знаємо, що\(P(n)\) це вірно для всіх\(n\). Це означає\[1+2+3+\cdots+n=\frac{n(n+1)}{2}\]
    для кожного\(n \in \mathbb{N}^{+}\).

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

    Доказ за допомогою індукції часто використовується для того, щоб показати, що дві функції\(f(n)\) і\(g(n)\) рівні. (Пропозиція\(8.1.4\) є прикладом цього, з\(f(n)=1+2+3+\cdots+n\) і\(g(n)=n(n+1) / 2\).) Базовий випадок зазвичай простий: обчислити\(f(1)\) і\(g(1)\), потім помітити, що вони рівні. З іншого боку, як правило, не відразу видно, як зробити індукційний крок, тому непогано почати з виконання деяких подряпин:

    • Запишіть бажане рівність\(f(k) \stackrel{?}{=} g(k)\).
    • Потім використовуйте алгебраїчні спрощення, щоб прийти до істинного твердження. У якийсь момент цих маніпуляцій ви будете використовувати індукційну гіпотезу для\(f(k − 1)\) заміни на\(g(k − 1)\), або навпаки.

    Доказ можна отримати, переписуючи ці алгебраїчні кроки в логічному порядку (бажано, як «однорядкове доказ» - рядок рівностей, що починається з\(f(k)\) і закінчується на\(g(k)\)).

    Наприклад, роботу з подряпиною, яка призвела до вищезазначеного підтвердження пропозиції,\(8.1.4\) можна знайти на малюнку\(8A\) нижче. При цьому алгебраїчні маніпуляції досить прості, але деякі проблеми значно складніше.

    clipboard_e5a4ba0cb953bb5112761711ff8765e42.png
    Малюнок\(8A.\) подряпин робота для доказу пропозиції\(8.1.4\).

    Ось ще один приклад, який досить простий:

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

    Для кожного\(n \in \mathbb{N}^{+}\) у нас є\[3+7+11+\cdots+(4 n-1)=2 n^{2}+n\]

    Доказ

    ДОКАЗ ІНДУКЦІЄЮ.

    \(P(n)\)Визначте, щоб бути твердженням\[3+7+11+\cdots+(4 n-1)=2 n^{2}+n .\]

    1. Базовий кейс. Бо\(n = 1\), ми маємо\[3+7+11+\cdots+(4 n-1)=3 \quad \text { and } \quad 2 n^{2}+n=2\left(1^{2}\right)+1=3 .\]
      Оскільки вони рівні,\(P(1)\) це правда.
    2. Індукційний крок. Припустімо\(P(k − 1)\), що це правда (і\(k \geq 2\)). Це означає, що\[3+7+11+\cdots+(4(k-1)-1)=2(k-1)^{2}+(k-1) .\]
      звідси\ [\ почати {вирівняні}
      3+7 &+11+\ cdots+ (4 k-1)\\
      & =( 3+7+11+\ cdots+ (4 (k-1) -1)) + (4 k-1)\\
      &=\ лівий (2 (k-1) ^ {2} + (k-1)\ праворуч) + (4 k-1)\\\
      =\ (2\ ліворуч (k^ {2} - 2 k+1\ праворуч) + (k-1)\ праворуч) + (4 k-1)\\
      &=\ ліворуч (2 k^ {2} -4 k+2\ праворуч) + (k-1) + (4 k-1)\\
      &= 2 k^ {2} +k,
      \ end {вирівняний}\]
      (Третя лінія: Індукційна гіпотеза)
      так\(P(k)\) вірно.

    Тому за принципом математичної індукції ми знаємо, що\(P(n)\) це вірно для всіх\(n\). Це означає\ [3+7+11+\ cdots+ (4 n-1) =2 n^ {2} +n
    для кожного\(n \in \mathbb{N}^{+}\).

    Вправа\(8.1.7\).

    Доведіть кожну формулу математичною індукцією.

    1. \(2+4+6+8+\cdots+2 n=n(n+1).\)
    2. \(1+3+5+7+\cdots+(2 n-1)=n^{2} .\)
    3. \(2+7+12+17+\cdots+(5 n-3)=\frac{n(5 n-1)}{2} .\)

    Позначення\(8.1.8\).

    Часто доводиться складати довгий список чисел (як у вищевказаних вправах), тому зручно мати для цього хороші позначення: якщо\(a_{1}, a_{2}, \ldots, a_{n}\) будь-яка послідовність чисел, то суму\(a_{1}+a_{2}+\cdots+a_{n}\) можна позначити\[\sum_{k=1}^{n} a_{k} .\]
    (Символ\(\sum\) - велика сигма, грецький варіант букви\(S\) — це означає «сума».)

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

    \(a_{1}, a_{2}, \ldots, a_{n}\)Дозволяти послідовність чисел. Потім:

    1. \(\sum_{k=1}^{1} a_{k}=a_{1}, \quad \sum_{k=1}^{2} a_{k}=a_{1}+a_{2}, \quad \text { and } \quad \sum_{k=1}^{3} a_{k}=a_{1}+a_{2}+a_{3} .\)
    2. \(\sum_{k=1}^{1} k=1, \quad \sum_{k=1}^{2} k=1+2=3, \quad \sum_{k=1}^{3} k=1+2+3=6.\)
    3. \(\sum_{k=1}^{n} k=1+2+3+\cdots+n.\)
    4. Для будь-якого\(n \in \mathbb{N}^{+}\), у нас є\(\sum_{k=1}^{n} a_{k}=\left(\sum_{k=1}^{n-1} a_{k}\right)+a_{n}.\)

    Вправа\(8.1.10\).

    1. У\(8.1.7\) Вправі ліва частина кожної формули - це сума. Запишіть кожну з цих сум в\(\sum\) -позначеннях.
    2. Покажіть, що (1) і (4) з прикладу\(8.1.9\) мають на увазі\(\sum_{k=1}^{0} a_{k}=0 .\)

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

    На етапі індукції доказу шляхом індукції ми хочемо довести\[\forall k \geq 2,(P(k-1) \Rightarrow P(k)) .\]
    Оскільки\(k\) це пов'язана («фіктивна») змінна в цьому твердженні, немає ніякої шкоди в заміні її іншою літерою: наприклад, якщо ви віддаєте перевагу, цілком прийнятно довести, скажімо,\[\forall i \geq 2,(P(i-1) \Rightarrow P(i)), \quad \text { or } \quad \forall n \geq 2,(P(n-1) \Rightarrow P(n)) .\]
    Це важливо пам'ятати, коли змінна вже\(k\) використовується для чогось іншого.

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

    Покажіть, що\(\sum_{k=1}^{n}(2 k-5)=n^{2}-4 n .\)

    Рішення

    ДОКАЗ ІНДУКЦІЄЮ.

    \(P(n)\)Визначте, щоб бути твердженням\[\sum_{k=1}^{n}(2 k-5)=n^{2}-4 n.\]

    1. Базовий кейс. Бо\(n = 1\), у нас є\[\sum_{k=1}^{n}(2 k-5)=\sum_{k=1}^{1}(2 k-5)=2(1)-5=-3=1^{2}-4(1)=n^{2}-4 n.\]
      Так Р (1) вірно.
    2. Індукційний крок. Припустимо\(n \geq 2\) і\(P(n − 1)\) вірно. Це означає, що\[\sum_{k=1}^{n-1}(2 k-5)=(n-1)^{2}-4(n-1).\]
      звідси\ [\ почати {вирівняний}
      \ sum_ {k=1} ^ {n} (2 к-5) &=\ лівий (\ sum_ {k=1} ^ {n-1} (2 k-5)\ праворуч) + (2 n-5)\\
      &=\ лівий ((n-1) ^ {2} -4 (n-1)\ праворуч) + (2 n-5)\\\
      &=\ ліворуч (\ ліворуч (n^ {2} -2 n+1\ праворуч) -4 n+4\ праворуч) + (2 n-5)\\
      &=n^ {2} -4 n,
      \ end {вирівняний}\]
      (Другий рядок: Індукційна гіпотеза)
      так\(P(n)\) вірно.

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

    Вправа\(8.1.13\).

    Доведіть кожну формулу індукцією.

    1. \(\sum_{k=1}^{n}(6 k+7)=3 n^{2}+10 n.\)
    2. \(\sum_{k=1}^{n}(4 k-5)=2 n^{2}-3 n.\)
    3. \(\sum_{k=1}^{n}(12 k-19)=6 n^{2}-13 n .\)
    4. \(\sum_{k=1}^{n}(3 k+11)=\frac{3 n^{2}+25 n}{2}.\)
    5. \(\sum_{k=1}^{n} 3^{k}=\frac{3^{n+1}-3}{2} .\)
    6. \(\sum_{k=1}^{n} 3^{k}=\frac{3^{n+1}-3}{2}.\)
    7. \(\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}.\)
    8. \(\text { (harder) } \sum_{k=1}^{n} k^{3}=\left(\frac{n(n+1)}{2}\right)^{2} .\)

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

    Якщо ви хочете довести, що\(P(k)\) це вірно для всіх\(k\), то Принцип індукції може бути застосований\(k\) в ролі\(n\). Це називається «індуктивним на»\(k\). Аналогічно замість неї може бути використана будь-яка інша буква\(n\).

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

    Покажіть, для всіх\(k \in \mathbb{N}^{+}\), що\[\sum_{i=1}^{k}\left(3 i^{2}-3 i+1\right)=k^{3} .\]

    Рішення

    ДОКАЗ ІНДУКЦІЄЮ.

    \(P(k)\)Визначте, щоб бути твердженням\[\sum_{i=1}^{k}\left(3 i^{2}-3 i+1\right)=k^{3} .\]

    1. Базовий кейс. Бо\(k = 1\), у нас\(P(1)\) є\[\sum_{i=1}^{k}\left(3 i^{2}-3 i+1\right)=\sum_{i=1}^{1}\left(3 i^{2}-3 i+1\right)=3(1)^{2}-3(1)+1=1=1^{3}=k^{3} .\]
      Так вірно.
    2. Індукційний крок. Припустимо\(k \geq 2\) і\(P(k − 1)\) вірно. Це означає, що\[\sum_{i=1}^{k-1}\left(3 i^{2}-3 i+1\right)=(k-1)^{3} .\]
      звідси\ [\ почати {вирівняний}
      \ sum_ {i = 1} ^ {k}\ ліворуч (3 i^ {2} -3 i+1\ праворуч) &=\ ліворуч (\ sum_ {i=1} ^ {k-1}\ ліворуч (3 i^ {2} -3 i+1\ праворуч)\\ праворуч) +\ лівий (3 k^ {2} -3 k+1\ праворуч) +\ лівий (3 k^ {2} -3 k+1\
      праворуч)\\ (k-1) ^ {3} +\ ліворуч (3 k^ {2} -3 k+1\ праворуч)\\
      &=\ ліворуч (k^ {3} -3 k^ {2} +3 k-1\ праворуч) +\ ліворуч (3 k^ {2} -3 k+1\ праворуч)\\
      &=k^ {3},
      \ end {вирівняний}\]
      (Другий рядок: Індукційна гіпотеза)
      так\(P(k)\) вірно.

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