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.
Liczby Bella
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Liczby Bella
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)!}}\)
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)!}}\)