Пункт 9

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

Если нам нужно доказать некоторое утверджение P(n) для всех n∈ℕ, можно доказать следующее:

{[P(0)],[∀n:P(n)⇒P(n+1)])

Это очевидным образом обобщается на множество X={(x_0),s((x_0)),s(s((x_0))),…}

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

Докажем, что ∀n∈ℕ,x≥-1:(1+x)n≥1+n*x

База: n=1

∀x≥-1:1+x≥1+x. Очевидно

Переход: n→n+1

1. (1+x)(n+1)≥1+(n+1)*x

2. (1+x)n⋅(1+x)≥1+n*x+x

3. (1+x)n+x⋅(1+x)n≥1+n*x+x

4. x⋅(1+x)n≥x

5. x⋅(1+n*x)≥x

6. x+n*x2≥x

7. ЧТД

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

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

Пример

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

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

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

Переход:

Либо число n простое - автоматически доказано, либо n - составное. Значит, ∃a≥2,b≥2:n=a*b. Используя полную индукцию, раскроем a и b как (∏_^)((a_𝑖)), (∏_^)((b_i)). Тогда, n=(∏_^)((a_i))⋅(∏_^)((b_i)). ЧТД