http://brain.fuw.edu.pl/edu/index.php?title=Indukcja_matematyczna&feed=atom&action=historyIndukcja matematyczna - Historia wersji2024-03-29T14:06:25ZHistoria wersji tej strony wikiMediaWiki 1.34.1http://brain.fuw.edu.pl/edu/index.php?title=Indukcja_matematyczna&diff=1138&oldid=prevAnula: Utworzono nową stronę "__NOTOC__ ==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..."2015-05-22T11:50:38Z<p>Utworzono nową stronę "__NOTOC__ ==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..."</p>
<p><b>Nowa strona</b></p><div>__NOTOC__<br />
<br />
==Zasada indukcji matematycznej==<br />
<br />
Zbiór liczb naturalnych posiada bardzo ważną własność, której często się używa w dowodach. Mówi ona że:<br />
<br />
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:<br />
<equation id="eq:1">Liczba 1 posiada tę własność (tzn. teza <math>T_1\;</math> jest prawdziwa),</equation><br />
<equation id="eq:2">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>)</equation><br />
<br />
'''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 &mdash; na mocy <xr id="eq:2">(%i)</xr> &mdash; prawdziwa jest również teza <math>T_2\;</math>. Skoro tak, to z <xr id="eq:2">(%i)</xr> prawdziwa jest również teza <math>T_3\;</math>, i znów używając <xr id="eq:2">(%i)</xr> prawdziwa jest teza <math>T_4\;</math> itd.<br />
<br />
===Przykład &mdash; Nierówność Bernoulliego===<br />
<br />
Dla każdej liczby naturalnej <math>n\;</math> i każdej liczby rzeczywistej <math>a\geq -1\;</math> zachodzi wzór<br />
<equation id="eq:3"><br />
<math>(1+a)^n \geq 1+ n a \;<br />
</math><br />
</equation><br />
<br />
#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.<br />
#Sprawdzamy prawdziwość implikacji <math>T_n\Longrightarrow T_{n+1}\;</math>.<br />
Zapiszmy prawą stronę <math>T_{n+1}\;</math>:<br />
<center><math><br />
(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></center><br />
(korzystamy z założenia o prawdziwości T_n oraz że <math>(1+a)\geq 0 \;</math>)<br><br />
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> &mdash; tzn. że nierówność <xr id="eq:3">(%i)</xr> jest prawdziwa <math>\forall \, n\in \mathbb N\;</math><br />
<br />
===Przykład &mdash; Dwumian Newtona===<br />
<br />
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''<br />
<equation id="eq:4"><math>\begin{matrix}<br />
\left(<br />
\begin{matrix}<br />
n\\k<br />
\end{matrix}<br />
\right)<br />
&=&<br />
\frac{n(n-1)(n-2)\dots(n-k+1)}{1\cdot 2 \cdot 3 \dots \cdot k}<br />
\\<br />
&=& \frac{n!}{k!(n-k)!}<br />
\end{matrix}\;\;<br />
</math></equation><br />
zakładamy, że <math>n\;</math> i <math>k\;</math> są to liczby naturalne, oraz <math>n\geq k\;</math>. Mamy:<br />
<center><math><br />
\left(<br />
\begin{matrix}<br />
n\\0<br />
\end{matrix}<br />
\right) = 1, \;\;\;\;\; \left(\begin{matrix} n\\n \end{matrix}<br />
\right)=1.<br />
\;</math></center><br />
<br />
Pokażemy teraz, że <math>\forall\, n, k \in \mathbb N\;</math>, <math>n\geq k\;</math> zachodzi<br />
<center><math><br />
\left(<br />
\begin{matrix} n\\k\end{matrix}\right)+\left(\begin{matrix}n\\k-1\end{matrix}\right)=\left(\begin{matrix} n+1\\k \end{matrix}<br />
\right).\;</math></center><br />
<br />
Liczymy bezpośrednio:<br />
<center><math><br />
\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}<br />
\;</math></center><br />
<br />
<center><math><br />
=<br />
\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).<br />
\;</math></center><br />
<br />
Teraz przystępujemy do udowodnienia ''wzoru dwumiennego Newtona'':<br />
====Twierdzenie====<br />
<br />
<math>\forall\, a,b \in \mathbb R\;</math>, <math>\forall\, n\in \mathbb N\;</math> zachodzi <br><br />
<equation id="eq:5"><math><br />
(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<br />
+\left(\begin{matrix}n\\n\end{matrix}\right)b^n.<br />
\;</math></equation><br />
<br />
<br />
====Uwaga====<br />
<br />
Dla <math>n=1\;</math> wzór <xr id="eq:5">(%i)</xr> jest oczywisty. Dla <math>n=2\;</math> i <math>n=3\;</math> wzór wzór <xr id="eq:5">(%i)</xr> 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>).<br />
<br />
====Dowód====<br />
Tak więc, zgodnie ze schematem dowodu indukcyjnego:<br />
<ol> <br />
<li>Teza <math>T_1\;</math> jest prawdziwa.</li><br />
<li> Aby pokazać wynikanie <math>T_n\Longrightarrow T_{n+1}\;</math>, weźmy prawą stronę równości <xr id="eq:5">(%i)</xr> 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 <br />
<center><br />
<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> <br />
</center><br />
a jest to właśnie lewa strona równości <xr id="eq:5">(%i)</xr> dla <math>n+1\;</math>. Zatem, możemy zakończyć dowód mówiąc, że</li><br />
<li> Równość <xr id="eq:5">(%i)</xr> jest prawdziwa dla każdego <math>n\in \mathbb N\;</math>.</li><br />
</ol><br />
====Uwaga====<br />
Wzór na dwumian Newtona daje się zapisać o wiele krócej używając symbolu ''sumy'':<br />
<math><br />
(a+b)^n = \sum^{n}_{k=0} \left(<br />
\begin{matrix}<br />
n\\k<br />
\end{matrix}<br />
\right) <br />
a^{n-k} b^k<br />
\;</math><br />
<br />
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>.<br />
<br />
===Przykład===<br />
<br />
(startuje się od <math>n_0>1\;</math>) Pokazać, że <math>\forall n>4\;</math> zachodzi <math>2^n>n^2\;</math>. <br />
<br />
===Przykład===<br />
<br />
(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 <br />
<center><math><br />
F_n= \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]<br />
\;</math></center></div>Anula