Naukowy.pl

Ścisłe => Matematyka => Kompendium => Wątek zaczęty przez: lemon w Wrzesień 09, 2008, 03:53:52 pm

Tytuł: [Ci?gi] Indukcja matematyczna
Wiadomość wysłana przez: lemon w Wrzesień 09, 2008, 03:53:52 pm
Indukcja matematyczna jest sposobem dowodzenia twierdze?, w których mowa o liczbach naturalnych. Dowód t? metod? musi przebiega? wed?ug ustalonego schematu:

Za?ó?my, ?e dany jest ci?g twierdze?: \fs2 T_1 , T_2 , T_3 , \text{...} , T_n. Wówczas sprawdzamy prawdziwo?? twierdzenia dla pocz?tkowej liczby naturalnej. Kolejnym krokiem jest udowodnienie prawdziwo?ci implikacji T_n \Rightarrow T_{n+1}. Jest to drugi krok indukcyjny.

Po uzyskaniu prawdziwo?ci obu kroków indukcyjnych stwierdzamy, ?e \fs2 \bigwedge_{n \in N} (dla ka?dego/dowolnego \fs2 n \in N) twierdzenie \fs2 T_n jest prawdziwe.

Przyk?ad 1
Udowodnij, ?e \fs2 \bigwedge_{n \in N} \quad 1+2+3+\text{...}+n=\frac{n(n+1)}{2}.

Dowód:
Pierwszy krok indukcyjny - sprawdzamy prawdziwo?? tweirdzenia dla pocz?tkowej liczby naturalnej, czyli 1.

\fs2 \text{L}=1
\fs2 \text{P}=\frac{1(1+1)}{2}=1
\fs2 \text{L}=\text{P}

Drugi krok indukcyjny - sprawdzamy prawdziwo?? twierdzenia dla n+1.

\fs2 \text{L} = 1+2+3+\text{...}+n+(n+1)= \frac{n(n+1)}{2} + (n+1) =\qquad (podstawiamy za \fs2 1+2+3+\text{...}+n wyra?enie \fs2 \frac{n(n+1)}{2}).
\fs2 = \frac{n(n+1)}{n}+\frac{2(n+1)}{2}=\frac{(n+1)(n+2)}{2} \qquad (grupujemy wyrazy wy?aczajac wspólny czynnik przed nawias).

\fs2 \text{P} = \frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}

\fs2 \text{L}=\text{P}

Oba kroki indukcyjne zasz?y prawid?owo, zatem twierdzenie zosta?o udowodnione.


Przyk?ad 2
Udowodnij, ?e \fs2 \bigwedge_{n \in N} \quad liczba \fs2 n^3+2n jest podzielna przez 3.

Dowód:
Sprawdzamy prawdziwo?? twierdzenia pocz?tkowej liczby naturalnej: \fs2 1^3 + 2 = 3
Otrzymana liczba 3 jest podzielna przez 3.

Drugi krok indykcyjny. Spradzamy, czy je?li twierdzenie jest prawdziwe dla n, to czy te? jest prawdziwe dla nast?pnej liczby naturalnej, czyli n+1.

(n+1)^3 +2(n+1)=n^3+3n^2+3n+1+2n+2=\underline{n^3+2n} + 3n^2+3n+3=n^3+2n+3(n^2+n+1)

W pierwszym kroku indukcyjnym udowodnili?my, ?e liczba \fs2 n^3+2n jest podzielna przez 3. Podzielelne jest tak?e wyra?enie \fs2 3(n^2+n+1), zatem ich suma tak?e jest podzielna przez 3.