indukcja matematyczna marcin: Jak to jest z indukcją matematyczną? Chodzi mi dokładnie o zadania z treścią, ponieważ zadania

	n(n + 1)
typu: 1 + 2 + 3 + .. + =		udowadniam bez problemu. Ale jak widzę zadanie z
	2

treścią to nie wiem za co się wziąć, od czego zacząć. Moglibyście mnie trochę podszkolić w tych klockach ? I są jakieś różne wersje indukcji?

marcin: Wypowie się ktoś?

Godzio: Są trzy kroki indukcyjne: 1. Sprawdzenie prawdziwości zdania dla n_o (w tym wypadku mamy n = 1) 2. Zakładamy prawdziwość dla pewnej liczby n ∊ N 3. Udowadniamy, że zdanie zachodzi dla (n + 1) No to lecimy: 1^o Dla n = 1 mamy:

	1 * (1 + 1)
L = 1, P =		= 1 ⇒ L = P − OK !
	2

2^o Załóżmy, że dla pewnego n ∊ N zachodzi:

	n(n + 1)
1 + 2 + ... + n =		, pokażemy że zachodzi dla n + 1
	2

Dowód: 1 + 2 + ... + n + (n + 1) =_{korzystamy z założenia indukcyjnego}

n(n + 1)		n(n + 1)		2(n + 1)		(n + 1)(n + 2)
	+ (n + 1) =		+		=
2		2		2		2

Co kończy dowód,

marcin: Godzio, jakbyś się wczytał w to co napisałem. To doszedłbyś do wniosku, że takie zadania nie sprawiają problemów. Jednak znacznie gorzej idą mi zadania z treścią, jak nie ma żadnych wzorów i nie dochodzi się do formy L = P. Mógłbyś to wytłumaczyć, ewentualnie podać jakieś przykłady. I jak to jest z tymi wersjami?

Godzio: A rzeczywiście, przeoczyłem "udowadniam bez problemu" Ale o jakich zadaniach mówisz ? Podaj może jakiś przykład, bo nie za bardzo wiem o co Ci chodzi

marcin: 1. Na płaszczyźnie narysowano n prostych, z których żadne dwie nie są równoległe ani żadne trzy

	n2 + n + 2
nie przecinają się w jednym punkcie. Udowodnij, że dzielą one płaszczyznę na
	2

obszarów. O takie zadania mi chodzi, gdzie nie ma się za zadanie udowodnienia wzoru.

marcin: Lub: 2. Udowodnij, że regiony, na które dzieli płaszczyznę n prostych można pomalować dwoma kolorami tak, aby sąsiednie regiony były w różnych kolorach. No i tutaj właśnie nie ma żadnego wzoru. Jak to pociągnąć za pomocą indukcji?

Godzio: No to lecimy, analogicznie: Dla n = 1 powinniśmy otrzymać 2 płaszczyzny:

1 + 1 + 2		4
	=		= 2 − OK !
2		2

	n2 + n + 2
Załóżmy, że n prostych (przy danych założeniach) dzieli płaszczyznę na
	2

	(n + 1)2 + (n + 1) + 2
płaszczyzny, pokażmy, że (n + 1) prostych dzieli płaszczyznę na
	2

	n2 + 2n + 1 + n + 1 + 2		n2 + n + 2		2n + 2
=		=		+		=
	2		2		2

	n2 + n + 2
=		+ n + 1 płaszczyzn.
	2

	n2 + n + 2
Wychodzimy od:		, mając tyle obszarów, rysujemy dodatkową prostą. I zadanie
	2

sprowadza się do pokazania, że mają tyle obszarów i prowadząc dodatkową prostą otrzymamy (n + 1) nowych obszarów, dobrze sobie to zobrazować, żeby wiedzieć z czym ma się do czynienia

marcin: A jak zadanie drugie? Bo tam nie ma już wzoru do udowodnienia.

marcin:

marcin: Aż takie to trudne?

Godzio: Ja Ci w nim niestety nie pomogę...

Mila: Matematyka dyskretna −Jarosław Grytczuk , Strona 12 Sciągnij .Jest ładnie wyjaśnione z okręgami Dużo pisania.

marcin: Milo, jakbyś mogła udzielić jakiś rad, wskazówek odnośnie tych zadań. Jak dostrzegać w nich takie indukcyjne rozwiązanie, bo ono nie jest takie typowe jak w szkole [jak choćby nawet podany przyklad w temacie].

Mila: Musisz przerobić trochę zadań, nie panikuj, będzie na ćwiczeniach. Szukasz analogii z podanymi zadaniami: w książce, na wykładzie, na ćwiczeniach.