$P(n)$ degeri $n$. Fibonacci sayisini veren bir $P$ polinomu var mi?

Question

$P(n)$ degeri $n$. Fibonacci sayisini veren (derecesi sonlu) bir $P$ polinomu var mi?

Var ise bu polinom nedir, yok ise olamayacagini ispatlayiniz.

Comments

Güzel bir soru.

İpucu: $\displaystyle \lim_{n\to\infty}\frac{P(n+1)}{P(n)}$ i düşünün.

---

$P(n+1)=P(n)+P(n-1)$ olması gerekmiyor mu? Tümevarımla ispatlanabilmesi için polinomların katsayılarının eşit olması gerekir. Fakat eşit dereceden olacaklarından başkatsayısı $a$ olan bir $P(n)$ polinomu olsaydı $P(n+1)$ ve $P(n-1)$ polinomlarının da başkatsayısı $a$ olacak. O halde polinomların birbirine eşit olabilmesi için $2a=a$ olacak ki denklemin kökü $a=0$ olur. Başkatsayı olabilmesi için $a\neq0$ olması gerektiğine göre çelişki elde ederiz. O halde fibonacci serisinin elemanlarını veren bir $P(n)$ polinomu yoktur?! Yaklaşımım bu hocam doğruluğundan çok çürütülebileceğine inanıyorum aslında ama maksat safımız belli olsun :)

---

Bu da çok güzel bir çözüm.

Polinomların hızlı artmaması ama Fibonacci sayılarını üstel artıyor olmasından dolayı (http://matkafasi.com/18738/fibonacci-dizisi-icin-kapali-bir-formul?show=18738#q18738) 

, benim ilk olarak aklıma yazdığım çözüm geldi.

---

Bir an çürütüldü sandım dedim içimden bu kadar çabuk mu :) Aynen galiba polinom yok fakat üstel fonksiyon çıkma ihtimali -tabii varsa- epey yüksek.

Answer 1

Dogan Donmez'in yorumda dedigini dusunelim. Bence gayet akillica ve bircok yerde kullanilabilinecek bir yontem. Tek sart gelecek limitin $1$ olmamasi. 

Fibonacci Dizisinin terimleri   $$F_n=\frac{[(\sqrt5+1)/2]^n-[(\sqrt5-1)/2]^n}{\sqrt5}$$ olarak yazilabilir.  Bu bilindik. (Baglanti)

Orana bakarsak $$\frac{F_{n+1}}{F_n}=\frac{[(\sqrt5+1)/2]^{n+1}-[(\sqrt5-1)/2]^{n+1}}{[(\sqrt5+1)/2]^n-[(\sqrt5-1)/2]^n}$$ $$=\frac{[(\sqrt5+1)/2]-[(\sqrt5-1)/2] \cdot[(\sqrt5-1)/(\sqrt5+1)]^n}{1+ [(\sqrt5-1)/(\sqrt5+1)]^n}$$ olur.

$|(\sqrt5-1)/(\sqrt5+1)|<1$ oldugundan $$\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\frac{\sqrt5+1}{2}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (\ne 1)$$ olur. 

Eger bir $P$ polinomu icin $P(n)=F_n$ her $n$ dogal sayisi icin saglansaydi $$\frac{\sqrt5+1}{2}=\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\lim_{n\to\infty}\frac{P({n+1})}{P(n)}=1$$ bize celiski verirdi. Demek ki boyle bir polinom olamazmis.

Comments

$F_n=\dfrac{[(\sqrt5+1)/2]^n-[(\sqrt5-1)/2]^n}{\sqrt5}$ ifadesi bir polinom biçiminde yazılabiliyor olsaydı

$$P(x)=\dfrac{[(\sqrt5+1)/2]^x-[(\sqrt5-1)/2]^x}{\sqrt5}$$

ifadesinin belli bir mertebeden sonra türevinin sıfır olması gerekirdi. Bir $m$ pozitif tam sayısı için sıfıra eşit olan bu $m$-inci türevi hesaplayalım:

$$\dfrac{d^mP}{dx^m}= \dfrac{\left(\ln \dfrac{\sqrt5+1}{2}\right)^m\left[\dfrac{\sqrt5+1}{2}\right]^x- \left(\ln \dfrac{\sqrt5-1}{2}\right)^m\left[\dfrac{\sqrt5-1}{2}\right]^x}{\sqrt5}$$

olup $x$'in her değeri için sıfıra eşit olmalıdır. Örneğin $x=0$ koyarsak böyle bir şeyin (türevin sıfıra eşit olmasının) mümkün olmadığını görürüz. Demek ki $F_n$ ifadesi bir polinom değildir.

---

$\forall n\in\mathbb{N}$ için $P(n)=F_n=\frac{[(\sqrt5+1)/2]^n-[(\sqrt5-1)/2]^n}{\sqrt5}$ olmasından  

$P(x)=\frac{[(\sqrt5+1)/2]^x-[(\sqrt5-1)/2]^x}{\sqrt5}$ olması gerektiği doğru değil. 

Örneğin,  $P(x)=0$ sabit polinomu ve $f(x)=\sin(\pi x)$ olmak üzere, $\forall n\in\mathbb{N}$ için $f(n)=P(n)$ ama  $\forall x\notin\mathbb{Z}$ için $P(x)\neq f(x)$

---

Doğan hocam, şöyle bir ekleme yaparsak çözüm düzelir sanıyorum. Bizim problemimizde $n>1$ iken $F_n$ artan bir fonksiyon oluşturuyor. Bu durumda sonsuz tane noktada $P(n)$ ile çakışıyor. Sabit olmayan bir $P(n)$ polinomudur bu. Öte taraftan $F_n$ bir polinom fonksiyonu olarak ifade edilemez. İfade ediliyor olduğunu kabul ederek bir çelişki elde etmeyi denedim. Bir de, üstel olarak artan bir ifadenin polinom olamayacağı barizdir diye düşündüm. Polinom gibi artsaydı $F_n$ nin karşılık geldiği artan polinomun türevi bir mertebeden sonra sıfır olurdu. Fakat üstel fonksiyonda böyle bir durum söz konusu olamaz. Türev almaya devam etsek bile hep o üstel fonksiyon var olur. Temel fikrim buydu.

Bir başka çözüm de şöyle olabilir. Yazarken aklıma geldi. Polinom biçiminde kurala sahip dizilerde ardışık farklar dizileri bir süre sonra sabit olur. Örneğin $n^2$ dizisinin terimleri 1, 4, 9, 16, ... iken ilk ardışık farklar 3, 5, 7, ... ve bunların ardışık farkları 2, 2, 2, ... dir. İkinci ardışık farkın sabit oluşu bu dizinin ikinci dereceden polinom kuralına sahip olduğunu gösterir. Fibonacci dizisinin bu ardışık farklarının asla sabit gelmeyeceğini göstermek gerekiyor. Bu da Fibonacci dizisinin $F_{n+2} - F_{n+1} = F_n$ yineleme bağıntısı aracılığı ile gösterilebilir diye umuyorum. (Bunu denemedim)