Mam pewną funkcję:
\(\displaystyle{ F(n) = \sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor } \frac{(n-x)!}{x! \cdot (n-2x)!}}\)
Po wypisaniu kilku pierwszych wartości wychodzi, że
\(\displaystyle{ F(n) = F_{n+1}}\) (n+1 liczba fibonacciego)
Niestety, nie umiem tego udowodnić. Ma ktoś jakiś pomysł?
Ciąg Fibonacciego
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Ciąg Fibonacciego
Można uzasadnić, że \(\displaystyle{ F(n)}\) spełnia to samo równanie rekurencyjne, co ciąg Fibonacciego, wówczas pozostanie już przeliczyć dwa pierwsze wyrazy.
Popatrzmy na to od tej strony: niech \(\displaystyle{ n\ge 1}\), wtedy dla parzystego \(\displaystyle{ n}\)
\(\displaystyle{ F(n-1)+F(n)=\sum_{x=0}^{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor } \frac{(n-1-x)!}{x! \cdot (n-1-2x)!}+\sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor } \frac{(n-x)!}{x! \cdot (n-2x)!}=\\=\sum_{x=0}^{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor }{n-1-x\choose x}+\sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor }{n-x \choose x}=\\=\sum_{x=1}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor }{n-x\choose x-1}+\sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor }{n-x \choose x}=\\=1+ \sum_{x=1}^{\left \lfloor{ \frac{n}{2} }\right \rfloor}\left[ {n-x \choose x-1}+{n-x \choose x}\right]=\\={n+1-0 \choose 0}+ \sum_{x=1}^{\left \lfloor{ \frac{n}{2} }\right \rfloor}{n+1-x \choose x}=\\= \sum_{x=0}^{\left \lfloor{ \frac{n+1}{2} }\right \rfloor}{n+1-x \choose x}=F(n+1)}\)
Co się zmieni, jeśli \(\displaystyle{ n}\) będzie nieparzyste? Po pierwsze, wówczas
\(\displaystyle{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor=\left \lfloor{ \frac{n}{2} }\right \rfloor}\), a po drugie
\(\displaystyle{ \left \lfloor{ \frac{n+1}{2}\right\rfloor \neq \left \lfloor{ \frac{n}{2}\right\rfloor}\).
Wówczas przesunięcie indeksów o \(\displaystyle{ 1}\) w tej sumie:
\(\displaystyle{ \sum_{x=0}^{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor }{n-1-x\choose x}}\)
do prowadzi nas, zamiast powyższej, do takiej sumy:
\(\displaystyle{ \sum_{x=1}^{ \left \lfloor{ \frac{n{\red+1}}{2} }\right \rfloor }{n-x\choose x-1}}\)
i pozostaje sprawdzić, że gdy \(\displaystyle{ n}\) jest nieparzyste, to
\(\displaystyle{ {n- \frac{n+1}{2} \choose \frac{n+1}{2} -1}={n+1-\frac{n+1}{2} \choose \frac{n+1}{2}}}\)
(po prawej ten brakujący wyraz \(\displaystyle{ F(n+1)}\))
a to jest prawda, bo obie strony równości wynoszą \(\displaystyle{ 1}\).
Tym samym pokazaliśmy, że dla dowolnego \(\displaystyle{ n\ge 1}\)
zachodzi: \(\displaystyle{ F(n-1)+F(n)=F(n+1)}\).
Wystarczy teraz zweryfikować, że \(\displaystyle{ F(0)=1, \ F(1)=1}\) a skończymy dowód, że
\(\displaystyle{ F(n)=F_{n+1}}\)
gdzie \(\displaystyle{ F_k}\) to \(\displaystyle{ k}\)-ta liczba Fibonacciego.
Popatrzmy na to od tej strony: niech \(\displaystyle{ n\ge 1}\), wtedy dla parzystego \(\displaystyle{ n}\)
\(\displaystyle{ F(n-1)+F(n)=\sum_{x=0}^{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor } \frac{(n-1-x)!}{x! \cdot (n-1-2x)!}+\sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor } \frac{(n-x)!}{x! \cdot (n-2x)!}=\\=\sum_{x=0}^{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor }{n-1-x\choose x}+\sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor }{n-x \choose x}=\\=\sum_{x=1}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor }{n-x\choose x-1}+\sum_{x=0}^{ \left \lfloor{ \frac{n}{2} }\right \rfloor }{n-x \choose x}=\\=1+ \sum_{x=1}^{\left \lfloor{ \frac{n}{2} }\right \rfloor}\left[ {n-x \choose x-1}+{n-x \choose x}\right]=\\={n+1-0 \choose 0}+ \sum_{x=1}^{\left \lfloor{ \frac{n}{2} }\right \rfloor}{n+1-x \choose x}=\\= \sum_{x=0}^{\left \lfloor{ \frac{n+1}{2} }\right \rfloor}{n+1-x \choose x}=F(n+1)}\)
Co się zmieni, jeśli \(\displaystyle{ n}\) będzie nieparzyste? Po pierwsze, wówczas
\(\displaystyle{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor=\left \lfloor{ \frac{n}{2} }\right \rfloor}\), a po drugie
\(\displaystyle{ \left \lfloor{ \frac{n+1}{2}\right\rfloor \neq \left \lfloor{ \frac{n}{2}\right\rfloor}\).
Wówczas przesunięcie indeksów o \(\displaystyle{ 1}\) w tej sumie:
\(\displaystyle{ \sum_{x=0}^{ \left \lfloor{ \frac{n-1}{2} }\right \rfloor }{n-1-x\choose x}}\)
do prowadzi nas, zamiast powyższej, do takiej sumy:
\(\displaystyle{ \sum_{x=1}^{ \left \lfloor{ \frac{n{\red+1}}{2} }\right \rfloor }{n-x\choose x-1}}\)
i pozostaje sprawdzić, że gdy \(\displaystyle{ n}\) jest nieparzyste, to
\(\displaystyle{ {n- \frac{n+1}{2} \choose \frac{n+1}{2} -1}={n+1-\frac{n+1}{2} \choose \frac{n+1}{2}}}\)
(po prawej ten brakujący wyraz \(\displaystyle{ F(n+1)}\))
a to jest prawda, bo obie strony równości wynoszą \(\displaystyle{ 1}\).
Tym samym pokazaliśmy, że dla dowolnego \(\displaystyle{ n\ge 1}\)
zachodzi: \(\displaystyle{ F(n-1)+F(n)=F(n+1)}\).
Wystarczy teraz zweryfikować, że \(\displaystyle{ F(0)=1, \ F(1)=1}\) a skończymy dowód, że
\(\displaystyle{ F(n)=F_{n+1}}\)
gdzie \(\displaystyle{ F_k}\) to \(\displaystyle{ k}\)-ta liczba Fibonacciego.