Doğrusal indirgemeli diziler ve bunların üretici fonksiyonları ile ilgili teoriyi kullanacağız:
Teorem: $P(x)$, $Q(x)$ iki polinom fonksiyon, $k=derQ>derP$ olsun. Bu durumda $$ \dfrac{P(x)}{Q(x)}= a_0 + a_1x+a_2x^2+a_3x^3+\cdots $$ üretici fonksiyonu yardımıyla tanımlı $(a_n)$ doğrusal indirgemeli dizisinin karakteristik polinomu $$ x^kQ \left(\dfrac{1}{x}\right) $$ biçimindedir.
Buna göre, $\dfrac{1}{1-x-x^2-x^3}$ için $Q(x)=1-x-x^2-x^3$ olup $(a_n)$ dizisinin karakteristik polinomu $$x^3Q \left(\dfrac{1}{x}\right)= x^3-x^2-x-1 \tag{1}$$ olur. Dolayısıyla $n\geq 0$ için $$a_{n+3}=a_{n+2}+a_{n+1}+a_{n} \tag{2}$$ bağıntısı elde edilir. Tek ihtiyacımız olan dizinin ilk üç terimidir. $a_0=1, a_1=1, a_2=2$ olduğunu soru metninde verdiğimiz geometrik seri açılımından elde edebiliyoruz. Çok fazla üç terimliyi açmamıza gerek yoktur elbette:
$\dfrac{1}{1-(x+x^2+x^3)}=1+(x+x^2+x^3)+(x+x^2+x^3)^2+\cdots = 1+x+2x^2+\cdots $ bizim için yeterli olacaktır. Böylece $a_3=a_2+a_1+a_0 = 2+1+1=4$ olur. Diğer terimleri de $(2)$ indirgeme bağıntısından kolayca hesaplanabilir. Buradan
$$(a_n)=(1,1,2,4,7,13, 24, 44, 81, 149, 274, 504, 927, \dots ) \tag{3}$$
olur. Bu listeye göre $n\geq 9$ için $a_n> (n+1)^2$ dir. $0\leq n\leq 8$ için $a_n = (n+1)^2$ olan doğal sayı değerleri $n=0$ ve $n=8$ olarak elde edilir.
Notlar: Teoremin sunulduğu ve ispatlandığı kaynak burada Coursera sitesinden Evgeny Smirnov hocanın ders videolarıdır. Fakat teoremin yazılışında ufak bir sorun olmuştur. Karakteristik polinomun $Q(x)$ olduğu yazılmıştır. Geçen yıl dersleri takip ederken hatayı şurada bildirdim. Bu kursun öğretim sorumlusu Yulia Kotelnikova da itirazımın haklı olduğunu ifade etmişti. Yani karakteristik polinom, yukarıdaki teoremde ifade ettiğim gibidir.( Başka kaynaklar da kontrol edilebilir.) Teoriyle ilgili daha fazla bilgi için Evgeny Smirnov'un Enumerative Combinatorics ders videoları takip edilebilir.