Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Бодлого №16307
Фибаночийн дарааллын ерөнхий гишүүнийг ердийн уламжлагч функцийн аргаар ол.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар: $F_0=0$, $F_1=1$, $F_{n}=F_{n-1}+F_{n-2}$, $n\geqslant 2$ дарааллыг Фибоначийн дараалал гэнэ.
$p(x)$ предикатын хувьд $$[p(x)]=\left\{\begin{array}{ll} 1 , & p(x)\text{ үнэн}\\ 0 , & p(x)\text{ худал}\\ \end{array}\right.$$ гэж тодорхойлдог.
$$\dfrac{1}{1-\alpha x}=1+\alpha x+\alpha^2 x^2+\dots+\alpha^n x^n+\dots$$
$p(x)$ предикатын хувьд $$[p(x)]=\left\{\begin{array}{ll} 1 , & p(x)\text{ үнэн}\\ 0 , & p(x)\text{ худал}\\ \end{array}\right.$$ гэж тодорхойлдог.
$$\dfrac{1}{1-\alpha x}=1+\alpha x+\alpha^2 x^2+\dots+\alpha^n x^n+\dots$$
Бодолт: Аливаа $n\in\mathbb Z$-ийн хувьд
ба $n<0$ үед $F_n=0$ байхаар $a$, $b$ тоонуудыг олъё. $n=0,1$ утгуудыг орлуулбал $$F_{0}=F_{-1}+F_{-2}+a[0=0]+b[0=1]$$ $$F_{1}=F_{0}+F_{-1}+a[1=0]+b[1=1]$$ буюу $$0=0+0+a\cdot 1+b\cdot 0$$ $$1=0+0+a\cdot 0+b\cdot 1$$ тул $a=0$, $b=1$ байна. Иймд $$F_{n}=F_{n-1}+F_{n-2}+[n=1]$$ байна. Үүний хоёр талыг $x^n$-ээр үржүүлбэл $$F_{n}x^n=F_{n-1}x^n+F_{n-2}x^n+[n=1]x^n$$ болох ба үүнийг бүх $n\in\mathbb Z$-ээр нийлбэрчилбэл $$\sum_{n}F_{n}x^n=x\sum_{n}F_{n-1}x^{n-1}+x^2\sum_{n}F_{n-2}x^{n-2}+\sum_{n}[n=1]x^n$$ $$f(x)=xf(x)+x^2f(x)+x\Rightarrow f(x)=\dfrac{x}{1-x-x^2}$$ болно. $$x^2-x-1=0\Rightarrow x_1=\dfrac{1+\sqrt{5}}{2}, x_2=\dfrac{1-\sqrt{5}}{2}$$ ба Виетийн теоремоор $x_1+x_2=1$, $x_1\cdot x_2=-1$ ба $(1-x_1x)(1-x_2x)=1-x-x^2$ байна. $$\dfrac{x}{1-x-x^2}=\dfrac{A}{1-x_1x}+\dfrac{B}{1-x_2x}$$ байх $A$, $B$ тоонуудыг олъё. $$x=A(1-x_2x)+B(1-x_1x)=A+B-(Ax_2+Bx_1)x$$ тул $A+B=0$, $Ax_2+Bx_1=-1$ болно. Эндээс $A(x_1-x_2)=1\Rightarrow A=\dfrac{1}{\sqrt{5}}$ ба $B=-\dfrac{1}{\sqrt{5}}$ болно. Эндээс $$\dfrac{x}{1-x-x^2}=\sum_{n\geqslant 0}\dfrac{1}{\sqrt{5}}(x_1^n-x_2^n)\cdot x^n$$ тул $$F_n=\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}$$ байна.
ба $n<0$ үед $F_n=0$ байхаар $a$, $b$ тоонуудыг олъё. $n=0,1$ утгуудыг орлуулбал $$F_{0}=F_{-1}+F_{-2}+a[0=0]+b[0=1]$$ $$F_{1}=F_{0}+F_{-1}+a[1=0]+b[1=1]$$ буюу $$0=0+0+a\cdot 1+b\cdot 0$$ $$1=0+0+a\cdot 0+b\cdot 1$$ тул $a=0$, $b=1$ байна. Иймд $$F_{n}=F_{n-1}+F_{n-2}+[n=1]$$ байна. Үүний хоёр талыг $x^n$-ээр үржүүлбэл $$F_{n}x^n=F_{n-1}x^n+F_{n-2}x^n+[n=1]x^n$$ болох ба үүнийг бүх $n\in\mathbb Z$-ээр нийлбэрчилбэл $$\sum_{n}F_{n}x^n=x\sum_{n}F_{n-1}x^{n-1}+x^2\sum_{n}F_{n-2}x^{n-2}+\sum_{n}[n=1]x^n$$ $$f(x)=xf(x)+x^2f(x)+x\Rightarrow f(x)=\dfrac{x}{1-x-x^2}$$ болно. $$x^2-x-1=0\Rightarrow x_1=\dfrac{1+\sqrt{5}}{2}, x_2=\dfrac{1-\sqrt{5}}{2}$$ ба Виетийн теоремоор $x_1+x_2=1$, $x_1\cdot x_2=-1$ ба $(1-x_1x)(1-x_2x)=1-x-x^2$ байна. $$\dfrac{x}{1-x-x^2}=\dfrac{A}{1-x_1x}+\dfrac{B}{1-x_2x}$$ байх $A$, $B$ тоонуудыг олъё. $$x=A(1-x_2x)+B(1-x_1x)=A+B-(Ax_2+Bx_1)x$$ тул $A+B=0$, $Ax_2+Bx_1=-1$ болно. Эндээс $A(x_1-x_2)=1\Rightarrow A=\dfrac{1}{\sqrt{5}}$ ба $B=-\dfrac{1}{\sqrt{5}}$ болно. Эндээс $$\dfrac{x}{1-x-x^2}=\sum_{n\geqslant 0}\dfrac{1}{\sqrt{5}}(x_1^n-x_2^n)\cdot x^n$$ тул $$F_n=\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}$$ байна.