Ctrl+K

Dwa inne dowody formuły Bineta

Dwa inne dowody formuły Bineta#

W tym pliku zweryfikujemy następujące twierdzenie

Ciąg liczb

\(F_{n}=\left\{\begin{array}{ll} n, & n=0,1\\ F_{n-1}+F_{n-2}, & n\geq 2 \end{array} \right.\)

posiada zwartą formę postaci

\(F_{n} = \frac{1}{\sqrt{5}}(\phi^n-(\widehat{\phi})^n)\)

gdzie \(\phi=\frac{1+\sqrt{5}}{2}\) and \(\widehat{\phi}=\frac{1-\sqrt{5}}{2}\).

Dowód 1: funkcje tworzące#

Rozważmy następujący szereg potęgowy:

\[F(x) =\sum_{n\geq 0} F_{n} x^n\]

Traktujemy go jako formalny szereg potęgowy, ignorując wszelkie kwestie związane ze zbieżnością (są niestotne).

Fib=function('Fib')
n=var('n')
k=var('k')
x=var('x')
F=sum(Fib(n)*x^n,n,0,oo)

eq1=(F==Fib(0)+Fib(1)*x+sum(Fib(n)*x^n,n,2,oo))

pretty_print(eq1)
\(\displaystyle {\sum_{n=0}^{+\infty} x^{n} {\rm Fib}\left(n\right)} = x {\rm Fib}\left(1\right) + {\rm Fib}\left(0\right) + {\sum_{n=2}^{+\infty} x^{n} {\rm Fib}\left(n\right)}\)
eq2=(F==Fib(0)+Fib(1)*x+sum(Fib(n+2)*x^(n+2),n,0,oo))
pretty_print(eq2)
\(\displaystyle {\sum_{n=0}^{+\infty} x^{n} {\rm Fib}\left(n\right)} = x {\rm Fib}\left(1\right) + {\rm Fib}\left(0\right) + {\sum_{n=0}^{+\infty} x^{n + 2} {\rm Fib}\left(n + 2\right)}\)
eq3=(F==Fib(0)+Fib(1)*x+sum((Fib(n+1)+Fib(n))*x^(n+2),n,0,oo))
pretty_print(eq3)
\(\displaystyle {\sum_{n=0}^{+\infty} x^{n} {\rm Fib}\left(n\right)} = x {\rm Fib}\left(1\right) + {\rm Fib}\left(0\right) + {\sum_{n=0}^{+\infty} x^{n + 2} {\left({\rm Fib}\left(n + 1\right) + {\rm Fib}\left(n\right)\right)}}\)
Fs=function('Fs')
eq4=(Fs(x)==Fib(0)+Fib(1)*x+Fs(x)*x+Fs(x)*x^2)
pretty_print(eq4)
\(\displaystyle {\rm Fs}\left(x\right) = x^{2} {\rm Fs}\left(x\right) + x {\rm Fib}\left(1\right) + x {\rm Fs}\left(x\right) + {\rm Fib}\left(0\right)\)
solv=solve(eq4,Fs(x))
pretty_print(solv[0])
\(\displaystyle {\rm Fs}\left(x\right) = -\frac{x {\rm Fib}\left(1\right) + {\rm Fib}\left(0\right)}{x^{2} + x - 1}\)
pretty_print(solv[0].subs({Fib(0):0,Fib(1):1}))
\(\displaystyle {\rm Fs}\left(x\right) = -\frac{x}{x^{2} + x - 1}\)
R.<T>=QQ[] # pierścień wielomianów zmiennej T
K.<phi>=NumberField(T^2-T-1)
R2.<x>=K[] # pierścień zmiennej x nad ciałem K
expr=x/(1-x-x^2)

expr.partial_fraction_decomposition()

(0, [(1/5*phi - 3/5)/(x - phi + 1), (-1/5*phi - 2/5)/(x + phi)])

A1=(2/5*phi - 1/5)
aa=phi
A2=(-2/5*phi + 1/5)
bb=1-phi
expr==A1/(1-x*aa)+A2/(1-x*bb)

True

Zatem formuła Bineta wynika z własności rozwinięcia szeregu geometrycznego.

\[\frac{1}{1-x\alpha} = \sum_{n\geq 0} \alpha^n x^n\]

Dowód 2: rozkład spektralny macierzy#

W tym dowodzie zmienimy perspektywę i będziemy rozważać zamiast pojedycznych liczb Fibonacciego wektory Fibonacciego i ich macierz generującą.

Niech \(v_n = (F_{n+1},F_{n})^{T}\) będzie wektorem kolumnowym oraz

\[\begin{split}m=\left(\begin{array}{rr} 1 & 1 \\ 1 & 0 \end{array}\right)\end{split}\]

macierzą. Zachodzi

\[v_{n+1}= m v_{n}\]

Macierz \(m\) ma bazę wektorów własnych \(v_{\phi}\) oraz \(v_{\widehat{\phi}}\).

m=matrix(K,2,2,[1,1,1,0])
reigen=m.right_eigenvectors()
print("Pierwsza wartość własna = ", reigen[0][0])
print("Pierwszy wektor własny = ", [tuple(x) for x in reigen[0][1]]) 
print("Druga wartość własna = ", reigen[1][0])
print("Drugi wektor własny = ", [tuple(x) for x in reigen[1][1]])

Pierwsza wartość własna =  phi
Pierwszy wektor własny =  [(1, phi - 1)]
Druga wartość własna =  -phi + 1
Drugi wektor własny =  [(1, -phi)]

Otrzymujemy zatem

\[v_n = \alpha(n) v_{\phi}+\beta(n)v_{\widehat{\phi}}\]

oraz

\[\alpha(n)\phi v_{\phi}+\beta(n)\widehat{\phi}v_{\widehat{\phi}} = m v_{n} = v_{n+1} = \alpha(n+1) v_{\phi}+\beta(n+1)v_{\widehat{\phi}}\]

i wykorzystując fakt, że \(v_{\phi}\) oraz \(v_{\widehat{\phi}}\) są bazą wektorów w przestrzeni liniowej \(K^2\) mamy

\[\alpha(n+1)=\alpha(n)\cdot \phi\]

i

\[\beta(n+1)=\beta(n)\cdot \widehat{\phi}\]

Rozwiązująć dla \(v_0 = (1,0)^{T}\) otrzymamy

\[\alpha(0)=\frac{\phi}{\sqrt{5}}\]

oraz

\[\beta(0)=\frac{\widehat{\phi}}{\sqrt{5}}\]
a,b,f=var('a,b,f')
solve([a+b-1,a*(f-1)+b*(-f)],a,b)

[[a == f/(2*f - 1), b == (f - 1)/(2*f - 1)]]

Hence

\[F_{n} =\frac{1}{\sqrt{5}}(\phi^n-(\widehat{\phi})^n)\]
m=matrix(2,2,[1,1,1,0])
m^2-m-identity_matrix(2)

[0 0]
[0 0]
Contents