notacja O - wyjasnienie

[coldrain]

Witam

W Ksiazce "Matematyka Dyskretna" w rozdziale 1.6 o notacji O jest taki zapis:
dla wszystkich \(\displaystyle{ n}\) mamy \(\displaystyle{ n \le 2^{n-1}}\)
Ogolnie,

\(\displaystyle{ n = 2 \cdot \frac{3}{2} \cdot \frac{4}{3} \cdot \frac{5}{4} \cdot ... \cdot \frac{n-1}{n-2} \cdot \frac{n}{n-1}}\)

skad sie wzial ten zapis? bo kompletnie go nie rozumiem.

[Crizz]

Przecież jeżeli skrócisz licznik każdego z ułamków z mianownikiem następnego, to otrzymasz n.

A tu chodzi o to, że:
\(\displaystyle{ 2=2}\)
\(\displaystyle{ \frac{3}{2} \le 2}\)
\(\displaystyle{ \frac{4}{3} \le 2}\)
...
\(\displaystyle{ \frac{n}{n-1} \le 2}\)

i mnożąc te nierwóności stronami, otrzymujesz \(\displaystyle{ n \le 2^{n-1}}\).

[coldrain]

hmm a moglbys mi rozpisac w krokach, po jakich przeksztalcenich dochodzi do tego ze \(\displaystyle{ n \le 2^{n-1}}\)?

nie moge do tego dojsc

[abc666]

No napisał ci. Bierzesz kolejne nierówności i mnożymy wszystkie lewy strony i wszystkie prawe, po lewej masz swój wzór na n a po prawej masz iloczyn n -1wójek czyli \(\displaystyle{ 2^{n-1}}\)

[coldrain]

moglby mi to ktos na przykladzie rozpisac w krokach, co sie po kolei robi? opis slowny mi kompletnie nie pomaga

[Afish]

Mnożysz po kolei lewe strony. I masz:
\(\displaystyle{ 2* \frac{3}{2} * \frac{4}{3} * ... * \frac{n}{n-1}}\)
Zauważ, że to się bardzo ładnie skraca. Gdy to wszystko wymnożysz, to wyjdzie właśnie n.
Teraz mnożysz po kolei prawe strony:
\(\displaystyle{ 2*2*2* ... * 2}\)
I tak dokładnie n-1 razy. Stąd wychodzi końcowa nierówność.