Udowodnij indukcyjnie i wzór
-
mantoo
- Użytkownik
- Posty: 7
- Rejestracja: 14 lis 2017, o 20:45
- Płeć: Mężczyzna
- Lokalizacja: Białystok
- Podziękował: 1 raz
Udowodnij indukcyjnie i wzór
Niech \(\displaystyle{ p_{n}}\) oznacza liczbę przekątnych w n-kącie foremnym. Zaproponuj wzór na \(\displaystyle{ p_{n}}\) oraz udowodnij indukcyjnie.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Udowodnij indukcyjnie i wzór
Odcinków łączących wierzchołki n-kąta foremnego masz dokładnie \(\displaystyle{ {n \choose 2}}\) - tyle samo, co podzbiorów dwuelementowych zbioru o \(\displaystyle{ n}\) elementach (z każdym takim odcinkiem jednoznacznie możesz skojarzyć parę wierzchołków). Od tego odejmujesz liczbę tych odcinków, które bynajmniej przekątnymi nie są, czyli są bokami - jest ich \(\displaystyle{ n}\), więc otrzymujesz \(\displaystyle{ {n \choose 2}-n}\) przekątnych. Ale powiedziałbym, że dowód indukcyjny w tym przypadku jest dość kłopotliwy. Trzeba by chyba po prostu opuścić założenie o foremności (bez niego też wzór działa, ale jak nie opuścimy tego założenia, to nie bardzo widać, jak to wykazać indukcyjnie).
\(\displaystyle{ 1^{\circ}}\) Łatwo sprawdzić na palcach, że ten wzorek daje, zgodnie z oczekiwaniami, \(\displaystyle{ p_3=0}\) oraz \(\displaystyle{ p_4=6-4=2}\).
\(\displaystyle{ 2^{\circ}}\) Powiedzmy, że wiemy, iż dla pewnego \(\displaystyle{ n \in \NN^+}\) w każdym n-kącie wypukłym (niekoniecznie foremnym) jest \(\displaystyle{ {n\choose 2}-n}\) przekątnych. Rozpatrzmy dowolny \(\displaystyle{ n+1}\)-kąt wypukły. Rozetnijmy go na trójkąt i n-kąt (wystarczy wybrać sobie pewien wierzchołek \(\displaystyle{ p}\) i dwa sąsiednie). Wówczas z założenia indukcyjnego mamy, że n-kąt ma \(\displaystyle{ {n \choose 2}-n}\) przekątnych, ponadto każdy wierzchołek n-kąta jest i wierzchołkiem \(\displaystyle{ n+1}\)-kąta. Przekątne \(\displaystyle{ n+1}\)-kąta, których nie policzyliśmy jako przekątnych n-kąta to dokładnie te, których jednym z wierzchołków jest nasz wyróżniony punkt \(\displaystyle{ p}\), zaś drugi wierzchołek to jeden spośród \(\displaystyle{ n+1-3=n-2}\) wierzchołków, które ani nie są tożsame z \(\displaystyle{ p}\), ani z nim nie sąsiadują, plus jeszcze jedna przekątna łącząca punkty sąsiadujące z punktem \(\displaystyle{ p}\). Zatem nasz \(\displaystyle{ n+1}\)-kąt ma \(\displaystyle{ {n \choose 2}-n+(n-2)+1={n+1 \choose 2}-(n+1)}\) (to trzeba przeliczyć, że ta równość zachodzi, nie będę rozpisywał, bo to nudy, zostawiam jako ćwiczenie) przekątnych, c.n.d.
\(\displaystyle{ 1^{\circ}}\) Łatwo sprawdzić na palcach, że ten wzorek daje, zgodnie z oczekiwaniami, \(\displaystyle{ p_3=0}\) oraz \(\displaystyle{ p_4=6-4=2}\).
\(\displaystyle{ 2^{\circ}}\) Powiedzmy, że wiemy, iż dla pewnego \(\displaystyle{ n \in \NN^+}\) w każdym n-kącie wypukłym (niekoniecznie foremnym) jest \(\displaystyle{ {n\choose 2}-n}\) przekątnych. Rozpatrzmy dowolny \(\displaystyle{ n+1}\)-kąt wypukły. Rozetnijmy go na trójkąt i n-kąt (wystarczy wybrać sobie pewien wierzchołek \(\displaystyle{ p}\) i dwa sąsiednie). Wówczas z założenia indukcyjnego mamy, że n-kąt ma \(\displaystyle{ {n \choose 2}-n}\) przekątnych, ponadto każdy wierzchołek n-kąta jest i wierzchołkiem \(\displaystyle{ n+1}\)-kąta. Przekątne \(\displaystyle{ n+1}\)-kąta, których nie policzyliśmy jako przekątnych n-kąta to dokładnie te, których jednym z wierzchołków jest nasz wyróżniony punkt \(\displaystyle{ p}\), zaś drugi wierzchołek to jeden spośród \(\displaystyle{ n+1-3=n-2}\) wierzchołków, które ani nie są tożsame z \(\displaystyle{ p}\), ani z nim nie sąsiadują, plus jeszcze jedna przekątna łącząca punkty sąsiadujące z punktem \(\displaystyle{ p}\). Zatem nasz \(\displaystyle{ n+1}\)-kąt ma \(\displaystyle{ {n \choose 2}-n+(n-2)+1={n+1 \choose 2}-(n+1)}\) (to trzeba przeliczyć, że ta równość zachodzi, nie będę rozpisywał, bo to nudy, zostawiam jako ćwiczenie) przekątnych, c.n.d.