Liczby Bella

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Nuna
Użytkownik
Użytkownik
Posty: 72
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 41 razy

Liczby Bella

Post autor: Nuna » 26 mar 2020, o 10:13

Mam problem z udowodnieniem nierówności
\(\displaystyle{ B_{n} < n!}\) dla \(\displaystyle{ n > 2}\)
gdzie \(\displaystyle{ B_{n}}\) jest liczbą Bella.
Jedyne co przychodzi mi do głowy to indukcja, ale może jest jakiś ładny dowód algebraiczny.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14627
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 96 razy
Pomógł: 4812 razy

Re: Liczby Bella

Post autor: Premislav » 26 mar 2020, o 11:13

Moim zdaniem najwygodniej byłoby udowadniać przez indukcję zupełną po \(\displaystyle{ n\ge 0}\), że \(\displaystyle{ B_{n}\le n!}\), przy czym ze względów technicznych bazę indukcji rozpisujemy zarówno dla \(\displaystyle{ n=0}\), jak i \(\displaystyle{ n=1}\), a potem zauważyć, że dla \(\displaystyle{ n>2}\) w jednym przejściu nierówność nieostrą można zastąpić przez ostrą.
Krok indukcyjny dla \(\displaystyle{ n\ge 1}\) wygląda wówczas tak:
\(\displaystyle{ B_{n+1}=\sum_{k=0}{n\choose k}B_{k}\le \sum_{k=0}^{n}{n\choose k}k!=n!\sum_{k=0}^{n}\frac{1}{(n-k)!}\\=n!\sum_{k=0}^{n}\frac{1}{k!}\le n!\left(3-\frac{1}{n}\right)\le (n+1)!}\)
Dwa komentarze tu się przydadzą:
komentarz nr 1 – dla \(\displaystyle{ n\ge 2}\) nierówność \(\displaystyle{ 3-\frac{1}{n}\le n+1}\) staje się ostra, gdyż po prawej mamy co najmniej \(\displaystyle{ 3}\), a po lewej liczbę ostro mniejszą niż \(\displaystyle{ 3}\);
komentarz nr 2 – przydałoby się może uzasadnić
\(\displaystyle{ \sum_{k=0}^{n}\frac{1}{k!}\le 3-\frac{1}{n}, \ n=1,2\ldots}\)
To też idzie indukcją po \(\displaystyle{ n}\), w kroku indukcyjnym \(\displaystyle{ \left(3-\frac{1}{n+1}\right)-\left(3-\frac{1}{n}\right)=\frac{1}{n(n+1)}\ge \frac{1}{(n+1)!}}\)

ODPOWIEDZ