Пункт 9

Метод математической индукции

Если нам нужно доказать некоторое утверджение P⁡(n) P of n для всех n∈ℕ n is a member of the natural numbers, можно доказать следующее:

{P⁡(0)∀n:P⁡(n)⇒P⁡(n+1) 2 cases Case 1: P of 0 Case 2: for all n colon P of n right double arrow P of open paren n plus 1 close paren

Это очевидным образом обобщается на множество X={x0,s⁡(x0),s⁡(s⁡(x0)),…} X equals the set x sub 0 comma s of open paren x sub 0 close paren comma s of s of open paren x sub 0 close paren comma dot dot dot

Пример: неравенство Бернулли

Докажем, что ∀n∈ℕ,x≥-1:(1+x)n≥1+n⁢x for all n is a member of the natural numbers comma x is greater than or equal to negative 1 colon open paren 1 plus x close paren to the n-th power is greater than or equal to 1 plus n x

База: n=1 n equals 1

∀x≥-1:1+x≥1+x for all x is greater than or equal to negative 1 colon 1 plus x is greater than or equal to 1 plus x. Очевидно

Переход: n→n+1 n right arrow n plus 1

  1. (1+x)n+1≥1+(n+1)⁢x open paren 1 plus x close paren raised to the n plus 1 power is greater than or equal to 1 plus open paren n plus 1 close paren times x

  2. (1+x)n⋅(1+x)≥1+n⁢x+x open paren 1 plus x close paren to the n-th power times open paren 1 plus x close paren is greater than or equal to 1 plus n x plus x

  3. (1+x)n+x⋅(1+x)n≥1+n⁢x+x open paren 1 plus x close paren to the n-th power plus x times open paren 1 plus x close paren to the n-th power is greater than or equal to 1 plus n x plus x

  4. x⋅(1+x)n≥x x times open paren 1 plus x close paren to the n-th power is greater than or equal to x

  5. x⋅(1+n⁢x)≥x x times open paren 1 plus n x close paren is greater than or equal to x

  6. x+n⁢x2≥x x plus n x squared is greater than or equal to x

  7. ЧТД

Метод полной математической индукции

По сути то же самое, но мы используем большее количество утверджений для "прошлых" значений n n, чем одно.

Пример

Утверджение: любое число n≥2 n is greater than or equal to 2 можно представить в виде произведения какого-то набора простых чисел

Доказательство:

База: n=2 n equals 2: очевидно

Переход:

Либо число n n простое - автоматически доказано, либо n n - составное. Значит, ∃a≥2,b≥2:n=a⁢b there exists a is greater than or equal to 2 comma b is greater than or equal to 2 colon n equals a b. Используя полную индукцию, раскроем a a и b b как ∏(a𝑖) the product of open paren a sub i close paren, ∏(bi) the product of open paren b sub i close paren. Тогда, n=∏(ai)⋅∏(bi) n equals the product of open paren a sub i close paren times the product of open paren b sub i close paren. ЧТД