$n^{f(n)}$ dizisinin sınırlı olma koşulu

Question

Kanıtlamak istediğim şey: $n^{f(n)}$ sınırlıdır ancak ve ancak $f(n)\to 0$. Ya da buna benzer bir şey.

Buradaki $f(n)$, $n$ değişkenine bağlı bir fonksiyon. Pozitif olma koşulu olmasa güzel olur ama gerekliyse pozitif olduğu varsayılabilir.

Bu sorunun soldan sağa kanıtı kolay: $f(n)$ dizisi sıfıra yakınsamasa bir $\epsilon$ pozitif sayısından büyük kalır, bu da $n^\epsilon<n^{f(n)}$ eşitsizliğini verir.

Soldan sağa kısmı için kanıt yapamadım, doğru olduğundan da şüpheliyim açıkçası.

Temel olarak; $n^{f(n)}$ dizisinin sınırlı olması için $f(n)$ dizisi üzerinde ne gibi bir gerek ve yeter koşul olmalıdır?

Örneğin, $c$ sabit bir sayı olmak üzere eğer $f(n)\leq c \frac{1}{n}$ gibi bir şey olsa, o zaman daha güçlü bir şey kanıtlanmış oluyor, $n^{f(n)}$ dizisinin $1$'e yakınsadığı çıkıyor buradan.

Comments

$x_n$ sinirliysa $\log x_n$ de sinirlidir civarinda seyler isine yaramaz mi? Bunun tersi dogru mu?

---

Güzel soruymuş, cevabı ben de merak ediyorum. Wolframalpha'da oynayarak biraz denedim. $f(n) = \frac{\log \log n}{\log n}$ alırsak, $f(n) \to 0$ ama $n^{f(n)} = \log n$ sınırlı değil. Yani ilk "ancak ve ancak" doğru değil, zaten sen de şüpheliymişsin. Ama nasıl bir koşul işe yarar bilemedim.

---

Şafak hocam, cevabın $\log n$ ile alakalı olduğunu tahmin ediyordum zaten. $\log$ grafiği "güzel" bir grafik olduğundan sınırlı bir parçasını aldığımızda $x$ değerleri de sınırlı olacaktır. Tersi de doğru oluyor yani. Zaten eğer $\log x_n< M$ ise $x_n < e^M$ oluyor.

Answer 1

$n^{f(n)}$'in sinirli olmasiyla $\log n^{f(n)}={f(n)}\log n$'in sinirli olmasi ayni sey. Bu da $f(n)\log n=O(1)$ demek.

Comments

kisa cevap, sasirtci..

---

o yüzden uzun başka bir cevap yazdım :)

Answer 2

Teorem şu şekilde olmalı sanıyorum.

Teorem: $n^{f(n)}$ sınırlıdır ancak ve ancak $c$ sabit bir sayı olmak üzere $f(n)<c \frac{1}{\log n}$

Kanıt: $(\Leftarrow)$ $n^{f(n)}$ sınırlı olmasın. $M>e^c$ olmak üzere bir sayı alalım. O zaman öyle bir $n_1$ var ki, $n_1^{f(n_1)}>M$ olur. Her iki tarafın logunu alalım: $$f(n_1) \log n_1 > \log M$$ Buradan da varsayımı kullanarak; $$\frac{\log M}{\log n_1} < f(n_1) < c \frac{1}{\log n_1}$$ elde ederiz. Bu da $\log M < c$ ve $M<e^c$ çelişkisini  verir.

$(\Rightarrow)$ $n^{f(n)}$, $M$ sayısı ile sınırlı olsun. Yani $n^{f(n)}<M$, bu da şunu verir: $$f(n) \log n < \log M$$ Yani; $$f(n)<\frac{\log M}{\log n}$$