Wykaż na 2 sposoby, że zachodzi tożsamość:
\(\displaystyle{ F_{n+1}={n\choose0}+{n-1\choose1}+{n-2\choose2}+{n-3\choose3}+...}\)
Jak ktoś widzi jeden sposób to oczywiście też może napisać.
Tożsamość z ciągiem Fibonacciego - 2 sposoby
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Tożsamość z ciągiem Fibonacciego - 2 sposoby
Trzeci sposób jest najfajniejszy.
Najpierw uogólnijmy współczynniki dwumianowe:
\(\displaystyle{ \binom{n}{k}=0}\), gdy \(\displaystyle{ n<k}\) lub \(\displaystyle{ k<0}\)
Sposób 1:
Oznaczmy:
\(\displaystyle{ H_n=\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+...+\binom{0}{n}}\).
Mamy:
\(\displaystyle{ H_0=\binom{0}{0}=1}\)
\(\displaystyle{ H_1=\binom{1}{0}+\binom{0}{1}=1+0=1}\)
oraz dla \(\displaystyle{ n>1}\)
\(\displaystyle{ H_{n+1}=H_{n}+H_{n-1}}\)
Co można tak zobaczyć:
\(\displaystyle{ {\begin{array}{ccccccc}
H_{n+1}&=&\binom{n+1}{0}&+&\binom{n}{1}&+&...\\\\
H_n&=&\binom{n}{0}&+&\binom{n-1}{1}&+&...\\\\
H_{n-1}&=&\binom{n-1}{-1}&+&\binom{n-2}{0}&+&...
\end{array}}\)
a dla uogólnionych współczynników dwumianowych zachodzi:
\(\displaystyle{ \binom{n+1}{k}=\binom{n}{k}+\binom{n-1}{k-1}}\)
Zatem \(\displaystyle{ H_n=F_n}\), bo te same dwa pierwsze wyrazy i ta sama rekurencją.
Sposób 2:
Rozważmy następujące zagadnienie:
Ile jest możliwych sposobów pokonania dystansu n krokami długości 1 lub 2.
Z jednej strony jest to liczba:
\(\displaystyle{ H_n=\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+...}\),
bo droga zawierająca \(\displaystyle{ k}\) kroków długości 2 składa się z \(\displaystyle{ n-k}\) kroków i takich dróg jest więc tyle, ile wyborów momentów, w których wykonujemy krok długości 2, czyli:
\(\displaystyle{ \binom{n-k}{k}}\)
czyli sumując wszystkie drogi otrzymujemy \(\displaystyle{ H_n}\).
Z drugiej strony każda droga długości \(\displaystyle{ n>1}\) kończy się krokiem długości 2 z pozycji \(\displaystyle{ n-1}\) lub krokiem długości 1 z pozycji \(\displaystyle{ n}\). Czyli liczba dróg długości n jest równa
(liczba dróg długości n-1 + liczba dróg długości n-2)
co po sprawdzeniu, że dróg długości 0 jest 1 (droga pusta), zaś długości 1 jest 1 (1 skok długości 1) dowodzi, że tych dróg jest \(\displaystyle{ F_n}\) i wobec tego \(\displaystyle{ F_n=H_n}\).
Sposób 3:
W wielomianie
\(\displaystyle{ \sum_{k=0}^n(x+x^2)^k}\)
spójrzmy na współczynnik przy \(\displaystyle{ x^n}\). Z jednej strony mamy:
\(\displaystyle{ \sum_{k=0}^n(x+x^2)^k=\sum_{k=0}^nx^k(1+x)^k=\sum_{k=1}^nx^k\left(...+\binom{k}{n-k}x^{n-k}+...\right)}\)
czyli ten współczynnik jest równy:
\(\displaystyle{ \sum_{k=0}^n\binom{k}{n-k}=\binom{0}{n}+\binom{1}{n-1}+...+\binom{n}{0}=\binom{n}{0}+\binom{n-1}{1}+...+\binom{0}{n}=H_n}\)
Z drugiej strony ze wzoru na sumę postępu geometrycznego mamy:
\(\displaystyle{ \sum_{k=0}^n(x+x^2)^k=\frac{1-(x+x^2)^{n+1}}{1-x-x^2}=}\)
\(\displaystyle{ =\frac{1-x^{n+1}(1+x)^{n+1}}{1-x-x^2}=\frac{1}{1-x-x^2}(1+x^{n+1}(1+x)^{n+1})}\)
Teraz trik. Niech
\(\displaystyle{ F(x)=\frac{1}{1-x-x^2}}\)
W kole o stosownym promieniu i środku w \(\displaystyle{ 0}\) funkcja ta rozwija się w szereg. Zauważmy, że interesuje nas współczynnik przy \(\displaystyle{ x^n}\) w tym szeregu, bo wielomian \(\displaystyle{ 1+x^{n+1}(1+x)^{n+1}}\) ma niezerowe współczynniki tylko przy \(\displaystyle{ x^0}\) i przy potęgach \(\displaystyle{ x}\) wyższych od \(\displaystyle{ n}\). Jak wiadomo (*) współczynnikami rozwinięcia \(\displaystyle{ F(x)}\) w szereg są \(\displaystyle{ F_n}\), więc przy \(\displaystyle{ x^n}\) w pierwotnym wyrażeniu stoi \(\displaystyle{ F_n}\), co kończy argument.
Najpierw uogólnijmy współczynniki dwumianowe:
\(\displaystyle{ \binom{n}{k}=0}\), gdy \(\displaystyle{ n<k}\) lub \(\displaystyle{ k<0}\)
Sposób 1:
Oznaczmy:
\(\displaystyle{ H_n=\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+...+\binom{0}{n}}\).
Mamy:
\(\displaystyle{ H_0=\binom{0}{0}=1}\)
\(\displaystyle{ H_1=\binom{1}{0}+\binom{0}{1}=1+0=1}\)
oraz dla \(\displaystyle{ n>1}\)
\(\displaystyle{ H_{n+1}=H_{n}+H_{n-1}}\)
Co można tak zobaczyć:
\(\displaystyle{ {\begin{array}{ccccccc}
H_{n+1}&=&\binom{n+1}{0}&+&\binom{n}{1}&+&...\\\\
H_n&=&\binom{n}{0}&+&\binom{n-1}{1}&+&...\\\\
H_{n-1}&=&\binom{n-1}{-1}&+&\binom{n-2}{0}&+&...
\end{array}}\)
a dla uogólnionych współczynników dwumianowych zachodzi:
\(\displaystyle{ \binom{n+1}{k}=\binom{n}{k}+\binom{n-1}{k-1}}\)
Zatem \(\displaystyle{ H_n=F_n}\), bo te same dwa pierwsze wyrazy i ta sama rekurencją.
Sposób 2:
Rozważmy następujące zagadnienie:
Ile jest możliwych sposobów pokonania dystansu n krokami długości 1 lub 2.
Z jednej strony jest to liczba:
\(\displaystyle{ H_n=\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+...}\),
bo droga zawierająca \(\displaystyle{ k}\) kroków długości 2 składa się z \(\displaystyle{ n-k}\) kroków i takich dróg jest więc tyle, ile wyborów momentów, w których wykonujemy krok długości 2, czyli:
\(\displaystyle{ \binom{n-k}{k}}\)
czyli sumując wszystkie drogi otrzymujemy \(\displaystyle{ H_n}\).
Z drugiej strony każda droga długości \(\displaystyle{ n>1}\) kończy się krokiem długości 2 z pozycji \(\displaystyle{ n-1}\) lub krokiem długości 1 z pozycji \(\displaystyle{ n}\). Czyli liczba dróg długości n jest równa
(liczba dróg długości n-1 + liczba dróg długości n-2)
co po sprawdzeniu, że dróg długości 0 jest 1 (droga pusta), zaś długości 1 jest 1 (1 skok długości 1) dowodzi, że tych dróg jest \(\displaystyle{ F_n}\) i wobec tego \(\displaystyle{ F_n=H_n}\).
Sposób 3:
W wielomianie
\(\displaystyle{ \sum_{k=0}^n(x+x^2)^k}\)
spójrzmy na współczynnik przy \(\displaystyle{ x^n}\). Z jednej strony mamy:
\(\displaystyle{ \sum_{k=0}^n(x+x^2)^k=\sum_{k=0}^nx^k(1+x)^k=\sum_{k=1}^nx^k\left(...+\binom{k}{n-k}x^{n-k}+...\right)}\)
czyli ten współczynnik jest równy:
\(\displaystyle{ \sum_{k=0}^n\binom{k}{n-k}=\binom{0}{n}+\binom{1}{n-1}+...+\binom{n}{0}=\binom{n}{0}+\binom{n-1}{1}+...+\binom{0}{n}=H_n}\)
Z drugiej strony ze wzoru na sumę postępu geometrycznego mamy:
\(\displaystyle{ \sum_{k=0}^n(x+x^2)^k=\frac{1-(x+x^2)^{n+1}}{1-x-x^2}=}\)
\(\displaystyle{ =\frac{1-x^{n+1}(1+x)^{n+1}}{1-x-x^2}=\frac{1}{1-x-x^2}(1+x^{n+1}(1+x)^{n+1})}\)
Teraz trik. Niech
\(\displaystyle{ F(x)=\frac{1}{1-x-x^2}}\)
W kole o stosownym promieniu i środku w \(\displaystyle{ 0}\) funkcja ta rozwija się w szereg. Zauważmy, że interesuje nas współczynnik przy \(\displaystyle{ x^n}\) w tym szeregu, bo wielomian \(\displaystyle{ 1+x^{n+1}(1+x)^{n+1}}\) ma niezerowe współczynniki tylko przy \(\displaystyle{ x^0}\) i przy potęgach \(\displaystyle{ x}\) wyższych od \(\displaystyle{ n}\). Jak wiadomo (*) współczynnikami rozwinięcia \(\displaystyle{ F(x)}\) w szereg są \(\displaystyle{ F_n}\), więc przy \(\displaystyle{ x^n}\) w pierwotnym wyrażeniu stoi \(\displaystyle{ F_n}\), co kończy argument.
(*):