Indukcja matematyczna

Indukcja matematyczna, zwana też indukcją zupełną, jest to metoda dowodzenia twierdzeń o liczbach naturalnych.

Niech T(n) oznacza formę zdaniową zmiennej n określoną w dziedzinie $\mathbb {N}$. Jeśli w miejsce n podstawimy dowolną liczbę naturalną, to T(n) stanie się zdaniem prawdziwym albo fałszywym, zależnie od wartości n. Jeżeli, na przykład, T(n) oznacza wypowiedź "n jest podzielne przez 3", to T(6) jest zdaniem prawdziwym, natomiast T(7) jest zdaniem fałszywym. Jeżeli T(n) oznacza nierówność n < n², to T(n) jest zdaniem prawdziwym dla każdej liczby naturalnej większej od 1, natomiast zdanie T(1) jest fałszywe.

Metoda indukcji matematycznej opiera się na następującej zasadzie:

Zasada indukcji matematycznej. Jeżeli

1. istnieje taka liczba naturalna n₀, że T(n₀) jest zdaniem prawdziwym,
2. dla każdej liczby naturalnej n $\geq$ n₀ prawdziwa jest implikacja T(n) $\Rightarrow$ T(n + 1),

to T(n) jest zdaniem prawdziwym dla każdej liczby naturalnej n $\geq$ n₀.

Przykład: Udowodnić, że dla każdej liczby naturalnej n $\geq$ 3 spełniona jest nierówność

2ⁿ > 2n.

Nierówność jest tu formą zdaniową T(n), n₀ = 3.

1. Dla n = 3 nierówność jest prawdziwa, ponieważ 2³ = 8 > 2 ^. 3 = 6. T(3) jest więc zdaniem prawdziwym.

2. Załóżmy, że nierówność jest prawdziwa dla liczby naturalnej n $\geq$ 3. Mnożąc tę nierówność obustronnie przez 2 dostajemy 2 ^. 2ⁿ > 2 ^. 2n, czyli 2ⁿ⁺¹ > 2n + 2n. Ponieważ dla każdego n $\geq$ 3 mamy 2n > 2, więc 2n + 2n > 2n + 2 = 2(n + 1). Stąd ostatecznie

2ⁿ⁺¹ > 2(n + 1).

Nierówność ta oznacza prawdziwość zdania T(n + 1). Wykazaliśmy zatem, że dla każdej liczby naturalnej n $\geq$ 3 prawdziwa jest implikacja T(n) $\Rightarrow$ T(n + 1), gdyż z prawdziwości jej poprzednika wynika prawdziwość następnika.

Ponieważ założenia zasady indukcji matematycznej są dla nierówności spełnione, więc ta nierówność jest prawdziwa dla każdego n $\geq$ 3.

Dowód przeprowadzony metodą indukcji matematycznej nazywamy dowodem indukcyjnym; składa się on z dwóch etapów:

1. sprawdzenia, że T(n₀) jest prawdziwe,

2. dowodu, że dla każdego n $\geq$ n₀ jeżeli T(n) jest prawdziwe, to T(n + 1) jest prawdziwe.

Ten drugi etap nazywamy krokiem indukcyjnym; zakładamy w nim, że dla liczby naturalnej n $\geq$ n₀ zdanie T(n) jest prawdziwe (tzw. hipoteza indukcyjna) i na tej podstawie dowodzimy prawdziwości zdania T(n + 1).

Oto jeszcze jeden przykład:

Przykład: Udowodnić, że dla każdego naturalnego n

1² +2² +...+ n² = $${\frac{{n}}{{6}}}$$(n + 1)(2n + 1).

Dowód indukcyjny, n₀ = 1.

1. Sprawdzamy, że równość jest prawdziwa dla n = 1:

1² = $${\frac{{1}}{{6}}}$$(1 + 1)(2 ^. 1 + 1) = 1.

2. Załóżmy, że równość jest prawdziwa dla liczby naturalnej n. Do obu stron tej równości dodajemy (n + 1)², więc

1² +2² +...+ n² + (n + 1)² = $${\frac{{n}}{{6}}}$$(n + 1)(2n + 1) + (n + 1)²

a następnie przekształcamy prawą stronę:

$${\frac{{n}}{{6}}} {\frac{{n+1}}{{6}}}$$

$${\frac{{n+1}}{{6}}} {\frac{{n+1}}{{6}}}$$ =

Stąd

1² +2² +...+ n² + (n + 1)² = $${\frac{{n+1}}{{6}}}$$[(n + 1) + 1] ^. [2(n + 1) + 1].

Ta równość różni się od równości, którą chcemy dowieść tylko tym, że mamy w niej n + 1 zamiast n. Dla każdej liczby naturalnej n prawdziwa jest więc implikacja T(n) $\Rightarrow$ T(n + 1), gdzie T(n) oznacza dowodzoną równość. Na mocy zasady indukcji matematycznej równość jest więc prawdziwa dla każdej liczby naturalnej n.

Za pomocą zasady indukcji matematycznej łatwo i szybko dowodzi się cały szereg charakterystycznych twierdzeń. Podajemy niektóre z nich.

Sumy potęg kolejnych liczb naturalnych.

1. $\sum_{{k=1}}^{n}$k = ${\frac{{n(n+1)}}{{2}}}$ = s₁
2. $\sum_{{k=1}}^{n}$k² = ${\frac{{n(n+1)(2n+1)}}{{6}}}$ = s₂ (patrz powyższy przykład)
3. $\sum_{{k=1}}^{n}$k³ = s₁²
4. $\sum_{{k=1}}^{n}$k⁴ = ${\frac{{1}}{{5}}}$s₂(3n² + 3n - 1)
5. $\sum_{{k=1}}^{n}$k⁵ = ${\frac{{1}}{{3}}}$s₁²(2n² + 2n - 1)
6. $\sum_{{k=1}}^{n}$k⁶ = ${\frac{{1}}{{7}}}$s₂(3n⁴ +6n³ - 3n + 1)
7. $\sum_{{k=1}}^{n}$k⁷ = ${\frac{{1}}{{6}}}$s₁²(3n⁴ +6n³ - n² - 4n + 2)
8. $\sum_{{k=1}}^{n}$k⁸ = ${\frac{{1}}{{15}}}$s₂(5n⁶ +15n⁵ +5n⁴ -15n³ - n² + 9n - 3)

Sumy potęg kolejnych nieparzystych liczb naturalnych.

1. $\sum_{{k=1}}^{n}$(2k - 1) = n² = $\sigma_{1}^{}$
2. $\sum_{{k=1}}^{n}$(2k - 1)² = ${\frac{{1}}{{3}}}$n(4n² -1) = $\sigma_{2}^{}$
3. $\sum_{{k=1}}^{n}$(2k - 1)³ = $\sigma_{1}^{}$(2n² - 1)
4. $\sum_{{k=1}}^{n}$(2k - 1)⁴ = ${\frac{{1}}{{5}}}$$\sigma_{2}^{}$(12n² - 7)
5. $\sum_{{k=1}}^{n}$(2k - 1)⁵ = ${\frac{{1}}{{3}}}$$\sigma_{1}^{}$(16n⁴ -20n² + 7)
6. $\sum_{{k=1}}^{n}$(2k - 1)⁶ = ${\frac{{1}}{{7}}}$$\sigma_{2}^{}$(48n⁴ -72n² + 31)

Podzielność.

1. 2| n² - n
2. 6| n³ - n
3. 30| n⁵ - n
4. 42| n⁷ - n
5. 546| n¹3 - n
6. 9| 10ⁿ - 1
7. 12| 10ⁿ - 4
8. 11| 10ⁿ - (- 1)ⁿ
9. 101| 10²ⁿ - (- 1)ⁿ
10. 1001| 10³ⁿ - (- 1)ⁿ
11. 7| 10³ⁿ⁺¹ -3(- 1)ⁿ
12. 13| 10³ⁿ⁺¹ +3(- 1)ⁿ
13. 14| 10³ⁿ⁺² -2(- 1)ⁿ
14. 52| 10³ⁿ⁺² +4(- 1)ⁿ
15. 11| 2⁶ⁿ⁺¹ +3²ⁿ⁺²
16. 10| 2²ⁿ - 6
17. 41| 5 ^. 7²⁽ⁿ⁺¹⁾ +2³ⁿ
18. 25| 2ⁿ⁺²3ⁿ + 5n - 4
19. 169| 3³ⁿ - 26n - 1
20. 11| 5⁵ⁿ⁺¹ +4⁵ⁿ⁺² +3⁵ⁿ

Nierówność Bernoulliego, jej uogólnienia i zastosowania.

1. (1 + a)ⁿ $\geq$ 1 + na, a > - 1 (Bernoulli, 1689)
2. (1 + a)ⁿ $\geq$ 1 + na + ${\frac{{n(n-1)}}{{2}}}$a², a $\geq$ 0
3. (1 + a)ⁿ $\geq$ 1 + na + ${\frac{{n(n-1)}}{{2}}}$a² + ${\frac{{n(n-1)(n-2)}}{{6}}}$a³, a > - 1
4. (1 + a)^1/n $\leq$ 1 + ${\frac{{a}}{{n}}}$, a > - 1
5. (1 + a)^1+1/n $\geq$ 1 + ${\frac{{a}}{{n(1+a)}}}$, a > - 1
6. (1 + a)^1+1/n $\geq$ 1 + (1 + ${\frac{{1}}{{n}}}$)a, a > - 1
7. (1 + a)^1+m/n $\geq$ 1 + (1 + ${\frac{{m}}{{n}}}$)a, a > - 1
8. (1 + a)^p/q $\geq$ 1 + ${\frac{{p}}{{q}}}$a, a > - 1, p $\geq$ q $\geq$ 1
9. (1 + a)^p/q $\leq$ 1 + ${\frac{{p}}{{q}}}$a, a > - 1, 1 $\leq$ p $\leq$ q

Ciąg Fibonacciego. Określamy

u₀ = 0,   u₁ = 1,

u_n+2 = u_n + u_n+1

1. $\sum_{{k=0}}^{n}$u_k = u_n+2 - 1
2. $\sum_{{k=0}}^{n}$u_2k+1 = u_2n+2
3. $\sum_{{k=0}}^{n}$u_2k = u_2n+1 - 1
4. $\sum_{{k=0}}^{{2n}}$(- 1)^ku_k = u_2n-1 - 1
5. $\sum_{{k=0}}^{{2n+1}}$(- 1)^k+1u_k = u_2n + 1
6. $\sum_{{k=0}}^{n}$u_k² = u_nu_n+1
7. $\sum_{{k=0}}^{{2n-1}}$u_ku_k+1 = u_2n²
8. u_n-1u_n+1 - u_n² = (- 1)ⁿ
9. u_n+1 = u_mu_n-m + u_m+1u_n-m+1, n $\geq$ m $\geq$ 0
10. u_2n+1 = u_n² + u_n+1²
11. u_2n = u_n+1² - u_n-1²
12. u_3n = u_n³ + u_n+1³ - u_n-1³
13. u_n⁴ = 1 + u_n-2u_n-1u_n+1u_n+2
14. $\sum_{{k=0}}^{n}$${\frac{{u_{k+2}}}{{u_{k+1}u_{k+3}}}}$ = ${\frac{{u_3}}{{u_1 u_2}}}$ - ${\frac{{u_{n+4}}}{{u_{n+2} u_{n+3}}}}$
15. u_n = ${\frac{{\alpha^n - \beta^n}}{{\alpha - \beta}}}$, gdzie $\alpha$ i $\beta$ są różnymi pierwiastkami równania
    x² = x + 1.