1.1 Udowodnić następującą zależność rekurencyjną:
\(\displaystyle{ a _{n}=\frac{1}{2}( 3^{n-1}+1- 2^{n} )}\)
1.2 Znaleźć równanie rekurencyjne dla \(\displaystyle{ g^*(n,k)}\) - liczby \(\displaystyle{ k}\) elementowych podzbiorów zbioru \(\displaystyle{ [n]}\) bez sąsiadów modulo \(\displaystyle{ n}\).
1.3 Udowodnić następującą zależność rekurencyjną:
\(\displaystyle{ F_{n+m}= F_{m} \cdot F_{n}+F _{m-1} \cdot F_{n-1}}\)
Czy ktos jest w stanie mi to wyłumaczyć vol.2
Czy ktos jest w stanie mi to wyłumaczyć vol.2
Ostatnio zmieniony 24 mar 2019, o 19:09 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
-
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
Czy ktos jest w stanie mi to wyłumaczyć vol.2
Ad. 1.1 Tutaj czegoś brakuje w treści zadania.
Ad. 1.2 co to są sąsiedzi modulo \(\displaystyle{ n}\)
Ad. 1.3 Zależność rekurencyjna, którą napisałeś, jest niepoprawna (choć blisko), powinna ona wyglądać tak:
\(\displaystyle{ F_{n+m}=F_{n+1}F_m+F_nF_{m-1}}\)
Można ją udowodnić za pomocą indukcji, na przykład po \(\displaystyle{ n\in \NN^+}\) przy ustalonym \(\displaystyle{ m}\), o schemacie \(\displaystyle{ \left(T(1)\wedge T(2)\wedge (\forall k\in \NN^+)(T(k)\wedge T(k+1)\implies T(k+2))\right)\implies (\forall k\in \NN^+)T(k)}\)
Krok indukcyjny (nie będę pisać całego rozwiązania): z zależności rekurencyjnej dla ciągu Fibonacciego mamy
\(\displaystyle{ F_{n+2}F_m+F_{n+1}F_{m-1}=F_{n+1}F_m+F_{n}F_m+F_nF_{m-1}+F_{n-1}F_{m-1}=\\=\left( F_{n+1}F_m+F_nF_{m-1}\right)+\left( F_nF_m+F_{n-1}F_{m-1}\right) =\\=[\text{ założenie indukcyjne }]=F_{m+n}+F_{m+n-1}=F_{m+n+1}}\)
Ad. 1.2 co to są sąsiedzi modulo \(\displaystyle{ n}\)
Ad. 1.3 Zależność rekurencyjna, którą napisałeś, jest niepoprawna (choć blisko), powinna ona wyglądać tak:
\(\displaystyle{ F_{n+m}=F_{n+1}F_m+F_nF_{m-1}}\)
Można ją udowodnić za pomocą indukcji, na przykład po \(\displaystyle{ n\in \NN^+}\) przy ustalonym \(\displaystyle{ m}\), o schemacie \(\displaystyle{ \left(T(1)\wedge T(2)\wedge (\forall k\in \NN^+)(T(k)\wedge T(k+1)\implies T(k+2))\right)\implies (\forall k\in \NN^+)T(k)}\)
Krok indukcyjny (nie będę pisać całego rozwiązania): z zależności rekurencyjnej dla ciągu Fibonacciego mamy
\(\displaystyle{ F_{n+2}F_m+F_{n+1}F_{m-1}=F_{n+1}F_m+F_{n}F_m+F_nF_{m-1}+F_{n-1}F_{m-1}=\\=\left( F_{n+1}F_m+F_nF_{m-1}\right)+\left( F_nF_m+F_{n-1}F_{m-1}\right) =\\=[\text{ założenie indukcyjne }]=F_{m+n}+F_{m+n-1}=F_{m+n+1}}\)
Czy ktos jest w stanie mi to wyłumaczyć vol.2
Treść zadania 1.1
Pokazać, że liczba podziałów zbioru \(\displaystyle{ [n]}\) na trzy niepuste zbiory wynosi.
Pokazać, że liczba podziałów zbioru \(\displaystyle{ [n]}\) na trzy niepuste zbiory wynosi.
Ostatnio zmieniony 24 mar 2019, o 19:48 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
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: Czy ktos jest w stanie mi to wyłumaczyć vol.2
Tak informacyjnie napiszę, że to są liczby Stirlinga II rodzaju.
Niech \(\displaystyle{ a_n}\) oznacza liczbę podziałów zbioru \(\displaystyle{ \left\{ 1, \ldots n\right\}}\) na trzy niepuste, parami rozłączne zbiory i niech \(\displaystyle{ b_n}\) oznacza liczbę podziałów tego samego zbioru na dwa niepuste, parami rozłączne zbiory.
Odnotujmy, że \(\displaystyle{ a_3=1}\). Ponadto gdy mamy zbiór o \(\displaystyle{ n+1}\) elementach, to weźmy zbiór złożony z pierwszych \(\displaystyle{ n}\) elementów. Możemy go podzielić na \(\displaystyle{ a_n}\) sposobów na trzy rozłączne niepuste, po czym na \(\displaystyle{ 3}\) sposoby wybrać ten podzbiór, do którego dorzucimy \(\displaystyle{ n+1}\). element, bądź na \(\displaystyle{ b_n}\) sposobów podzielić ten zbiór \(\displaystyle{ n}\) pierwszych elementów na dwa rozłączne niepuste, a jako trzeci zbiór wziąć singleton \(\displaystyle{ n+1}\). elementu.
Stąd wynika zależność rekurencyjna:
\(\displaystyle{ a_{n+1}=3a_n+b_n}\).
Wyznaczmy teraz wzór na \(\displaystyle{ b_n}\): odnotujmy, że \(\displaystyle{ b_2=1}\), a ponadto gdy mamy zbiór \(\displaystyle{ \left\{ 1, \ldots n+1\right\}}\), to możemy wziąć jego podzbiór złożony z \(\displaystyle{ n}\) pierwszych elementów i podzielić go na dwa rozłączne niepuste na \(\displaystyle{ b_n}\) sposobów, po czym na \(\displaystyle{ 2}\) sposoby wybrać, do którego dorzucimy \(\displaystyle{ n+1}\) albo wziąć zbiór cały \(\displaystyle{ \left\{ 1, \ldots n\right\}}\) jako ten pierwszy zbiór i \(\displaystyle{ \left\{ n+1\right\}}\) jako ten drugi. Stąd wynika zależność:
\(\displaystyle{ b_{n+1}=2b_n+1}\), dzięki której możemy już łatwo udowodnić indukcyjnie, że
\(\displaystyle{ b_n=2^{n-1}-1}\) (ja wzór \(\displaystyle{ b_n}\) znalazłem inaczej, ale dajmy spokój).
Otrzymaliśmy więc:
\(\displaystyle{ a_{n+1}=3a_n+2^{n-1}-1}\), ponadto \(\displaystyle{ a_3=1}\). Niech teraz \(\displaystyle{ n>3}\). Zapiszmy zależności:
\(\displaystyle{ a_n=3a_{n-1}+2^{n-2}-1\\ a_{n-1}=3a_{n-2}+2^{n-3}-1\\ \ldots \\a_4=3a_3+2^2-1}\)
Teraz mnożymy drugą równość przez \(\displaystyle{ 3}\), następną przez \(\displaystyle{ 9}\) i tak dalej, dodajemy wszystkie równości stronami, skracamy co się da i dostajemy
\(\displaystyle{ a_n=3^{n-3}a_3+ \sum_{k=2}^{n-1}\left( 2^k-1\right)3^{n-k-1}=\\=3^{n-3}+ \sum_{k=2}^{n-2}\left( 2^k-1\right)3^{n-k-2}}\)
czy jakoś tak…
Tę sumę sam już sobie zwiń (ciągi geometryczne, lol), okaż trochę zaangażowania, proszę.
-- 24 mar 2019, o 20:51 --
A jak nie chcesz zwijać tych ciągów geometrycznych, to sprawdź, że równanie rekurencyjne, które otrzymałem, spełnia też ten Twój ciąg \(\displaystyle{ \frac{1}{2}( 3^{n-1}+1- 2^{n} )}\) i że dla \(\displaystyle{ n=3}\) się zgadza.
Niech \(\displaystyle{ a_n}\) oznacza liczbę podziałów zbioru \(\displaystyle{ \left\{ 1, \ldots n\right\}}\) na trzy niepuste, parami rozłączne zbiory i niech \(\displaystyle{ b_n}\) oznacza liczbę podziałów tego samego zbioru na dwa niepuste, parami rozłączne zbiory.
Odnotujmy, że \(\displaystyle{ a_3=1}\). Ponadto gdy mamy zbiór o \(\displaystyle{ n+1}\) elementach, to weźmy zbiór złożony z pierwszych \(\displaystyle{ n}\) elementów. Możemy go podzielić na \(\displaystyle{ a_n}\) sposobów na trzy rozłączne niepuste, po czym na \(\displaystyle{ 3}\) sposoby wybrać ten podzbiór, do którego dorzucimy \(\displaystyle{ n+1}\). element, bądź na \(\displaystyle{ b_n}\) sposobów podzielić ten zbiór \(\displaystyle{ n}\) pierwszych elementów na dwa rozłączne niepuste, a jako trzeci zbiór wziąć singleton \(\displaystyle{ n+1}\). elementu.
Stąd wynika zależność rekurencyjna:
\(\displaystyle{ a_{n+1}=3a_n+b_n}\).
Wyznaczmy teraz wzór na \(\displaystyle{ b_n}\): odnotujmy, że \(\displaystyle{ b_2=1}\), a ponadto gdy mamy zbiór \(\displaystyle{ \left\{ 1, \ldots n+1\right\}}\), to możemy wziąć jego podzbiór złożony z \(\displaystyle{ n}\) pierwszych elementów i podzielić go na dwa rozłączne niepuste na \(\displaystyle{ b_n}\) sposobów, po czym na \(\displaystyle{ 2}\) sposoby wybrać, do którego dorzucimy \(\displaystyle{ n+1}\) albo wziąć zbiór cały \(\displaystyle{ \left\{ 1, \ldots n\right\}}\) jako ten pierwszy zbiór i \(\displaystyle{ \left\{ n+1\right\}}\) jako ten drugi. Stąd wynika zależność:
\(\displaystyle{ b_{n+1}=2b_n+1}\), dzięki której możemy już łatwo udowodnić indukcyjnie, że
\(\displaystyle{ b_n=2^{n-1}-1}\) (ja wzór \(\displaystyle{ b_n}\) znalazłem inaczej, ale dajmy spokój).
Otrzymaliśmy więc:
\(\displaystyle{ a_{n+1}=3a_n+2^{n-1}-1}\), ponadto \(\displaystyle{ a_3=1}\). Niech teraz \(\displaystyle{ n>3}\). Zapiszmy zależności:
\(\displaystyle{ a_n=3a_{n-1}+2^{n-2}-1\\ a_{n-1}=3a_{n-2}+2^{n-3}-1\\ \ldots \\a_4=3a_3+2^2-1}\)
Teraz mnożymy drugą równość przez \(\displaystyle{ 3}\), następną przez \(\displaystyle{ 9}\) i tak dalej, dodajemy wszystkie równości stronami, skracamy co się da i dostajemy
\(\displaystyle{ a_n=3^{n-3}a_3+ \sum_{k=2}^{n-1}\left( 2^k-1\right)3^{n-k-1}=\\=3^{n-3}+ \sum_{k=2}^{n-2}\left( 2^k-1\right)3^{n-k-2}}\)
czy jakoś tak…
Tę sumę sam już sobie zwiń (ciągi geometryczne, lol), okaż trochę zaangażowania, proszę.
-- 24 mar 2019, o 20:51 --
A jak nie chcesz zwijać tych ciągów geometrycznych, to sprawdź, że równanie rekurencyjne, które otrzymałem, spełnia też ten Twój ciąg \(\displaystyle{ \frac{1}{2}( 3^{n-1}+1- 2^{n} )}\) i że dla \(\displaystyle{ n=3}\) się zgadza.