Indukcja matematyczna

Zasada indukcji matematycznej

Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że:

Niech będzie dana jakaś własność liczb naturalnych (nazwijmy ją tezą indukcyjną) [math]T_n\;[/math],która spełnia następujące warunki:

Liczba 1 posiada tę własność (tzn. teza [math]T_1\;[/math] jest prawdziwa),

Jeśli liczba [math]n\;[/math] posiada tę własność, to posiada ją również liczba [math]n+1\;[/math] (tzn. prawdziwa jest implikacja: [math]T_n\Longrightarrow T_{n+1}\;[/math])

Zasada indukcji oznacza, że przy powyższych założeniach, każda liczba naturalna posiada tę własność (tzn. teza [math]T_n\;[/math] jest prawdziwa dla każdej [math]n\in \mathbb N\;[/math]). Zasada indukcji odpowiada następującej intuicji: Jeśli prawdziwa jest teza [math]T_1\;[/math], to — na mocy (2) — prawdziwa jest również teza [math]T_2\;[/math]. Skoro tak, to z (2) prawdziwa jest również teza [math]T_3\;[/math], i znów używając (2) prawdziwa jest teza [math]T_4\;[/math] itd.

Przykład — Nierówność Bernoulliego

Dla każdej liczby naturalnej [math]n\;[/math] i każdej liczby rzeczywistej [math]a\geq -1\;[/math] zachodzi wzór

[math](1+a)^n \geq 1+ n a \; [/math]

1. Sprawdzamy prawdziwość tezy [math]T_1\;[/math], tzn. czy nierówność jest prawdziwa dla [math]n=1\;[/math]. Mamy: [math]1+a \geq 1+ a\;[/math] czyli ok.
2. Sprawdzamy prawdziwość implikacji [math]T_n\Longrightarrow T_{n+1}\;[/math].

Zapiszmy prawą stronę [math]T_{n+1}\;[/math]:

[math] (1+a)^{n+1} = (1+a)^n(1+a) \geq (1+na)(1+a) = 1+(n+1)a + na^2 \geq 1+ (n+1)a\;[/math]

(korzystamy z założenia o prawdziwości T_n oraz że [math](1+a)\geq 0 \;[/math])
czyli, zakładając prawdziwósć tezy [math]T_n\;[/math], otrzymaliśmy prawdziwość; tezy [math]T_{n+1}\;[/math]. Z zasady indukcji wynika więc, że teza [math]T_n\;[/math] jest prawdziwa dla każej [math]n\in \mathbb N\;[/math] — tzn. że nierówność (3) jest prawdziwa [math]\forall \, n\in \mathbb N\;[/math]

Przykład — Dwumian Newtona

Najsampierw jednak zdefiniujemy (a dla tych, co znają, przypomnimy) symbol silnia: [math]n!=1\cdot 2 \cdot 3 \dots (n-1) \cdot n\;[/math], (przyjmujemy też, że [math]0!=1\;[/math]), a następnie współczynniki Newtona

[math]\begin{matrix} \left( \begin{matrix} n\\k \end{matrix} \right) &=& \frac{n(n-1)(n-2)\dots(n-k+1)}{1\cdot 2 \cdot 3 \dots \cdot k} \\ &=& \frac{n!}{k!(n-k)!} \end{matrix}\;\; [/math]

zakładamy, że [math]n\;[/math] i [math]k\;[/math] są to liczby naturalne, oraz [math]n\geq k\;[/math]. Mamy:

[math] \left( \begin{matrix} n\\0 \end{matrix} \right) = 1, \;\;\;\;\; \left(\begin{matrix} n\\n \end{matrix} \right)=1. \;[/math]

Pokażemy teraz, że [math]\forall\, n, k \in \mathbb N\;[/math], [math]n\geq k\;[/math] zachodzi

[math] \left( \begin{matrix} n\\k\end{matrix}\right)+\left(\begin{matrix}n\\k-1\end{matrix}\right)=\left(\begin{matrix} n+1\\k \end{matrix} \right).\;[/math]

Liczymy bezpośrednio:

[math] \left( \begin{matrix}n\\k\end{matrix}\right)+\left(\begin{matrix}n\\k-1 \end{matrix}\right)=\frac{n(n-1)(n-2)\dots(n-k+1)}{1\cdot 2 \cdot 3 \dots \cdot k}+\frac{n(n-1)(n-2)\dots(n-k+2)}{1\cdot 2 \cdot 3 \dots \cdot (k-1)}\cdot\frac{k}{k} \;[/math] [math] = \frac{n(n-1)(n-2)\dots(n-k+2)(n-k+1+k)}{1\cdot 2 \cdot 3 \dots \cdot k} = \left(\begin{matrix} n+1\\k\end{matrix}\right). \;[/math]

Teraz przystępujemy do udowodnienia wzoru dwumiennego Newtona:

Twierdzenie

[math]\forall\, a,b \in \mathbb R\;[/math], [math]\forall\, n\in \mathbb N\;[/math] zachodzi

[math] (a+b)^n= a^n + \left(\begin{matrix}n\\1\end{matrix}\right)a^{n-1}b+\left(\begin{matrix} n\\2\end{matrix}\right)a^{n-2}b^2+\dots+\left(\begin{matrix}n\\k\end{matrix}\right) a^{n-k}b^k+\dots +\left(\begin{matrix}n\\n\end{matrix}\right)b^n. \;[/math]

Uwaga

Dla [math]n=1\;[/math] wzór (5) jest oczywisty. Dla [math]n=2\;[/math] i [math]n=3\;[/math] wzór wzór (5) powinien być znany ze szkoły średniej (a jeśli nie jest, niech Czytelnik sprawdzi, że [math](a+b)^2=a^2+2ab+b^2\;[/math]; [math](a+b)^3=a^3+ 3 a^2 b + 3 a b^2 + b^3\;[/math]).

Dowód

Tak więc, zgodnie ze schematem dowodu indukcyjnego:

1. Teza [math]T_1\;[/math] jest prawdziwa.
2. Aby pokazać wynikanie [math]T_n\Longrightarrow T_{n+1}\;[/math], weźmy prawą stronę równości (5) dla [math]n+1\;[/math]. Mamy [math](a+b)^{n+1} = (a+b)^n(a+b) = (a+b)^n a + (a+b)^n b, \;[/math] i korzystając teraz z założenia o prawdziwości [math]T_n\;[/math], mamy

   [math]\begin{matrix} (a+b)^{n+1} =\;a^{n+1} +\left(\begin{matrix}n\\1\end{matrix}\right)a^{n}b+\left(\begin{matrix}n\\2\end{matrix}\right)a^{n-1}b^2+\dots+\left(\begin{matrix}n\\k\end{matrix}\right)a^{n-k+1}b^k+\dots+\left(\begin{matrix}n\\n\end{matrix}\right)a b^n + a^n b +\left(\begin{matrix}n\\1\end{matrix}\right)a^{n-1}b^2+\ldots\\+\left(\begin{matrix}n\\k-1\end{matrix}\right)a^{n-k+1}b^k+\ldots+\left(\begin{matrix}n+1\\n\end{matrix}\right)a b^{n}+b^{n+1}= a^{n+1} +\left(\begin{matrix} n+1\\1\end{matrix}\right) a^{n}b+ \dots+\left(\begin{matrix}n+1\\k\end{matrix}\right) a^{n-k+1}b^k+\dots+\left(\begin{matrix}n+1\\n\end{matrix}\right) a b^n + b^{n+1}\end{matrix},\;[/math]

   a jest to właśnie lewa strona równości (5) dla [math]n+1\;[/math]. Zatem, możemy zakończyć dowód mówiąc, że
3. Równość (5) jest prawdziwa dla każdego [math]n\in \mathbb N\;[/math].

Uwaga

Wzór na dwumian Newtona daje się zapisać o wiele krócej używając symbolu sumy: [math] (a+b)^n = \sum^{n}_{k=0} \left( \begin{matrix} n\\k \end{matrix} \right) a^{n-k} b^k \;[/math]

Tu symbol: [math]\sum^{n}_{k=0} A_k\;[/math] oznacza, że należy utworzyć sumę [math]n+1\;[/math] składników, które powstają z wyrażenia [math]A_k\;[/math] przez podstawianie na miejsce [math]k\;[/math] kolejno liczb [math]0, 1, 2,\dots, n\;[/math].

Przykład

(startuje się od [math]n_0\gt 1\;[/math]) Pokazać, że [math]\forall n\gt 4\;[/math] zachodzi [math]2^n\gt n^2\;[/math].

Przykład

(używa się tezy nie tylko [math]T_n\;[/math], ale też [math]T_{n-1}\;[/math] aby pokazać prawdziwość [math]T_{n+1}\;[/math]) Ciąg Fibonacciego. Określony jest on rekurencyjnie: [math]F_1 =F_2=1, F_n = F_{n-1} + F_{n-2}\;[/math]. Pokazać, że dla dowolnego [math]n\in \mathbb N\;[/math] zachodzi

[math] F_n= \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right] \;[/math]