Dowodzenie tożsamości na liczbach Fibonacciego

Dowodzenie tożsamości na liczbach Fibonacciego#

Niech $F_n$ oznacza $n$-tą liczbę Fibonacciego określoną wzorem

$F_n=\left\{\begin{array}{cc} n & n=0,1 \\ F_{n-1}+F_{n-2} & n\geq 2\end{array}\right.$

Niech $\phi$ oznacza dodatni pierwiastek wielomianu $x^2-x-1$

x=var('x')
pol=x^2-x-1
roots=pol.roots()
pretty_print(roots)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\left(-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}, 1\right), \left(\frac{1}{2} \, \sqrt{5} + \frac{1}{2}, 1\right)\right]$

[x[0] for x in roots if bool(x[0]>0)] #sprawdzamy, który pierwiastek jest dodatni

[1/2*sqrt(5) + 1/2]

phi=1/2*sqrt(5) + 1/2

phi

1/2*sqrt(5) + 1/2

type(phi) #to jest dokładne wyrażenie symboliczne

<type 'sage.symbolic.expression.Expression'>

(phi^2-phi-1).simplify_full() #sprawdzamy, że wyrażenie faktycznie jest pierwiastkiem wyjściowego wielomianu

Formuła Bineta#

Dla każdej liczby całkowitej $n\geq 0$ zachodzi

$F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n \right)$

gdzie $\phi=\frac{1}{2} \, \sqrt{5} + \frac{1}{2}$ oraz $\hat{\phi}=-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}$

Wskazówka:#

Możemy wykorzystać SageMath do produkowania formuł matematycznych w LaTeX:

latex(‘expression’)

Ćw. 1: Tożsamość Cassiniego#

$F_n^2 - F_{n+1}F_{n-1}=(-1)^{n-1}$

phi= 1/2*sqrt(5) + 1/2
phihat=-1/2*sqrt(5) + 1/2
def FibBin(n):
    return 1/sqrt(5)*(phi^n-phihat^n)

bool(FibBin(10).simplify_full() ==  fibonacci(10))

True

n=var('n')

pretty_print((FibBin(n)^2-FibBin(n+1)*FibBin(n-1)).simplify_full())

$\newcommand{\Bold}[1]{\mathbf{#1}}-{\left(\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n} {\left(-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n}$

(phi*phihat).simplify_full()

-1

Tożsamość jest udowodniona

Ćw. 2: Tożsamość Catalana#

$F_n^2-F_{n+r}F_{n-r}=(-1)^{n-r}F_{r}^2$

r=var('r')
pretty_print(((FibBin(n)^2-FibBin(n+r)*FibBin(n-r))/(FibBin(r)^2)).simplify_full())

$\newcommand{\Bold}[1]{\mathbf{#1}}{\left(\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n - r} {\left(-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n - r}$

Ćw. 3: Tożsamość Ocagne’a#

$F_{r} F_{n+1}-F_{r+1}F_{n}=(-1)^n F_{r-n}$

pretty_print(((FibBin(r)*FibBin(n+1)-FibBin(r+1)*FibBin(n))/(FibBin(r-n))).simplify_full())

$\newcommand{\Bold}[1]{\mathbf{#1}}{\left(\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n} {\left(-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n}$

Ćw. 4: Tożsamość z sumą#

$\sum_{i=1}^{n}F_{i}=F_{n+2}-1$

i=var('i')
pretty_print((sum(FibBin(i),i,0,n)/(FibBin(n+2)-1)).simplify_full())

$\newcommand{\Bold}[1]{\mathbf{#1}}1$

Ćw. 5: Kolejna tożsamość z sumą#

$\sum_{i=1}^{n}F_{i}^2=F_{n}F_{n+1}$

s1=sum(FibBin(i)^2,i,1,n)
s2=(FibBin(n)*FibBin(n+1))

pretty_print((s1-s2).simplify_full())

$\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{5} \, {\left(2 \, \left(-1\right)^{n} {\left(\sqrt{5} + 1\right)}^{n} {\left(\sqrt{5} - 1\right)}^{n} - {\left({\left(\sqrt{5} {\left(\sqrt{5} - 3\right)}^{n} - {\left(\sqrt{5} - 3\right)}^{n}\right)} \left(-1\right)^{n} - {\left(\sqrt{5} + 3\right)}^{n} {\left(\sqrt{5} + 1\right)}\right)} 2^{n} - 2^{2 \, n + 1} \left(-1\right)^{n} + \sqrt{5} {\left(\sqrt{5} - 1\right)}^{2 \, n} - {\left(\sqrt{5} + 1\right)}^{2 \, n + 1} - {\left(\sqrt{5} - 1\right)}^{2 \, n}\right)} 2^{-2 \, n - 1}$

#bez założeń nie da się wyewaluować poniższej formuły (dlaczego??)
assume(n,'integer')
((-1)^(2*n)).simplify()

assume(n>0);
pretty_print((s1).subs(n=2*n).canonicalize_radical().factor())

$\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{5} \, {\left(\sqrt{5} {\left(\sqrt{5} + 3\right)}^{2 \, n} - \sqrt{5} {\left(\sqrt{5} - 3\right)}^{2 \, n} - 2^{2 \, n + 1} + {\left(\sqrt{5} + 3\right)}^{2 \, n} + {\left(\sqrt{5} - 3\right)}^{2 \, n}\right)} 2^{-2 \, n - 1}$

(s1-s2).simplify_full() #SageMath poległ na sprawdzenie, że wyrażenie jest zerem

1/5*(2*(-1)^n*(sqrt(5) + 1)^n*(sqrt(5) - 1)^n - ((sqrt(5)*(sqrt(5) - 3)^n - (sqrt(5) - 3)^n)*(-1)^n - (sqrt(5) + 3)^n*(sqrt(5) + 1))*2^n - 2^(2*n + 1)*(-1)^n + sqrt(5)*(sqrt(5) - 1)^(2*n) - (sqrt(5) + 1)^(2*n + 1) - (sqrt(5) - 1)^(2*n))*2^(-2*n - 1)

assumptions(n) # możemy sprawdzić jakie założenia zostały poczynione

[n is integer, n > 0]

#forget() ##forget the assumptions

Wyzwanie: Udowodnij eliptyczną tożsamość Warda#

$F_{4n+2}F_2^3-F_{2n+4}F_{2n}^3+F_{2n+2}^3 F_{2n-2}=0$ for all $n\geq 0$.

(FibBin(4*n+2)*FibBin(2)^3-FibBin(2*n+4)*FibBin(2*n)^3+FibBin(2*n+2)^3*FibBin(2*n-2)).subs(n=50).simplify_full()