Ciąg Fibonacciego

[El3na]

W jaki sposób wykazać,że:

\(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\)

Należy tu wykorzystać tą zależność,że \(\displaystyle{ F_1=F_2=1, F_n = F_{n-1} + F_{n-2}}\) ?

[Jan Kraszewski]

W jaki sposób wykazać,że:

\(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\)

Indukcyjnie. Wygodniej będzie zapisać tezę tak:

\(\displaystyle{ F_1 + F_2 + ... + F_n+1 = F_{n+2}.}\)

Należy tu wykorzystać tą zależność,że \(\displaystyle{ F_1=F_2=1, F_n = F_{n-1} + F_{n-2}}\) ?

A jak chcesz udowodnić własność ciągu Fibonacciego nie odwołując się do jego definicji?

JK

[Premislav]

Zamiast udowadniać to indukcyjnie można też skorzystać z funkcji tworzących.
\(\displaystyle{ F_1+F_2+\ldots+F_n=F_0+F_1+\ldots+F_n}\) (ta równość zachodzi, gdyż \(\displaystyle{ F_0=0}\)) to splot \(\displaystyle{ F_n}\) i ciągu stałego \(\displaystyle{ b_n=1}\).
Funkcja tworząca ciągu \(\displaystyle{ (b_n)}\) to \(\displaystyle{ \sum_{n=0}^{\infty}x^n=\frac{1}{1-x}}\).
Funkcją tworzącą ciągu \(\displaystyle{ (F_n)}\) jest \(\displaystyle{ \frac{x}{1-x-x^2}}\):
oznaczmy funkcję tworzącą ciągu \(\displaystyle{ (F_n)}\) przez \(\displaystyle{ F(x)}\), wtedy mamy
\(\displaystyle{ F_{n+2}=F_{n+1}+F_n\\ \sum_{n=0}^{\infty} F_{n+2}x^n= \sum_{n=0}^{\infty}F_{n+1}x^n+ \sum_{n=0}^{\infty} F_n x^n\\ \sum_{n=0}^{\infty} F_{n+2}x^{n+2}= x\sum_{n=0}^{\infty}F_{n+1}x^{n+1}+ x^2\sum_{n=0}^{\infty} F_n x^n\\ F(x)-F_0 -F_1 x=x(F(x)-F_0)+x^2F(x)\\ F(x)(1-x-x^2)=x\\ F(x)=\frac{x}{1-x-x^2}}\)

Ponadto funkcja tworząca splotu ciągów to iloczyn ich funkcji tworzących, zatem
funkcja tworząca \(\displaystyle{ F_1+F_2+\ldots+F_n}\) ma postać
\(\displaystyle{ G(x)=F(x)\cdot \frac{1}{1-x}=\frac{x}{(1-x)(1-x-x^2)}}\),
natomiast funkcja tworząca ciągu o n-tym wyrazie \(\displaystyle{ F_{n+2}-1}\) to
\(\displaystyle{ \frac{1}{x^2}\left(F(x)-F_0-F_1 x\right)-\frac{1}{1-x}=\frac{1}{x^2}\left( \frac{x}{1-x-x^2} -x-\frac{x^2}{1-x}\right)}\)
i ponieważ funkcja tworząca jednoznacznie wyznacza ciąg, więc wystarczy sprawdzić, że
\(\displaystyle{ \frac{x}{(1-x-x^2)(1-x)}=\frac{1}{x^2}\left( \frac{x}{1-x-x^2} -x-\frac{x^2}{1-x}\right)}\),
co pozostawiam jako ćwiczenie dla autorki wątku.

[Jan Kraszewski]

Zamiast udowadniać to indukcyjnie można też skorzystać z funkcji tworzących.

To było dość... zabawne (w świetle tego, że dowód indukcyjny zajmuje ze 3 linijki).

JK

[Premislav]

To dobrze, ponieważ to miał być żart.

[Jan Kraszewski]

To dobrze, ponieważ to miał być żart.

Ja stary jestem i te współczesne młodzieżowe żarty słabo chwytam...

JK

[d3bora]

Wykazać,że: \(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\)
Czy takie rozwiązanie jest ok?
Wykazuję indukcyjnie:
-dla \(\displaystyle{ n = 1}\)
\(\displaystyle{ F_1 = F_3 - 1 \\
F_1 =F_2 + F_1 - 1 \\
F_2=1}\)
-założenie dla \(\displaystyle{ n \geq 1 , n \in \mathbb{N}}\)
\(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\)

-sprawdzenie dla \(\displaystyle{ n + 1}\)
\(\displaystyle{ F_1 + F_2 + ... + F_n + F_{n+1}= F_{n+3} - 1 \\
F_{n+2} - 1 + F_{n+1} = F_{n+3} -1 \\
F_{n+3} = F_{n+2} + F_{n+1}}\)
ostatnia równość wynika z definicji ciągu więc wyjściowa równość \(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\) jest prawdziwa.

[Jan Kraszewski]

-dla \(\displaystyle{ n = 1}\)
\(\displaystyle{ F_1 = F_3 - 1 \\
F_1 =F_2 + F_1 - 1 \\
F_2=1}\)

Dobrze, ale nieelegancko. Lepiej wygląda to tak:

\(\displaystyle{ F_3 - 1=F_2 + F_1 - 1=1+F_1-1=F_1.}\)

-założenie dla \(\displaystyle{ n \geq 1,n \in \mathbb{N}}\)
\(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\)

-sprawdzenie dla \(\displaystyle{ n + 1}\)
\(\displaystyle{ F_1 + F_2 + ... + F_n + F_{n+1}= F_{n+3} - 1 \\
F_{n+2} - 1 + F_{n+1} = F_{n+3} -1 \\
F_{n+3} = F_{n+2} + F_{n+1}}\)
ostatnia równość wynika z definicji ciągu więc wyjściowa równość \(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\) jest prawdziwa.

No i znów - rachunki są dobre, ale mnie ich prezentacja trochę zgrzyta. Ja napisałbym tak:

Ustalmy dowolne \(\displaystyle{ n \geq 1,n \in \mathbb{N}}\) takie, że \(\displaystyle{ F_1 + F_2 + ... + F_n = F_{n+2} - 1}\). Wtedy

\(\displaystyle{ F_1 + F_2 + ... + F_n + F_{n+1}\stackrel{zal.\ ind.}{=}F_{n+2} - 1 + F_{n+1}=(F_{n+2} + F_{n+1})-1=F_{n+3} -1.}\)

Zatem na mocy Zasady Indukcji Matematycznej teza jest prawdziwa.

JK