suma liczb naturalnych
suma liczb naturalnych
Pokazać, że dla każdej liczby naturalnej zachodzi równość : \(\displaystyle{ \sum_{i=0}^{n} 2 ^{n-i} {n+i \choose i} =2 ^{2n}}\).
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
suma liczb naturalnych
Da się zrobić indukcyjnie, ale to dość pracochłonne (sprawdziłem empirycznie).
W Matematyce konkretnej ta tożsamość to natomiast prosty wniosek z ogólniejszych zależności (dość skomplikowanych).
Q.
W Matematyce konkretnej ta tożsamość to natomiast prosty wniosek z ogólniejszych zależności (dość skomplikowanych).
Q.
-
SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
suma liczb naturalnych
A ja pokusiłem się o dowód kombinatoryczny i poszło prawie od razu ^^ :
Wykażemy, że wyrażenie \(\displaystyle{ \sum_{i=0}^{n} 2 ^{n-i} {n+i \choose i}}\) jest równe liczbie podzbiorów zbioru \(\displaystyle{ X=\{1,2,\ldots,2n\}}\), czyli \(\displaystyle{ 2^{2n}}\).
Oznaczmy \(\displaystyle{ S_i=\{1, 2,\ldots,i\}}\). Niech funkcja \(\displaystyle{ f}\) każdemu podzbiorowi \(\displaystyle{ Y}\) zbioru \(\displaystyle{ X}\) przyporządkuje największy taki indeks
\(\displaystyle{ k\in\{0,1\ldots,n\}}\), że moc co najmniej jednego ze zbiorów \(\displaystyle{ Y \cap S_{n+k}}\) lub \(\displaystyle{ (S_{2n}\backslash Y) \cap S_{n+k}}\) wynosi
\(\displaystyle{ n}\). Mówiąc obrazowo, szukamy największego \(\displaystyle{ k\leq n}\) takiego, że spośród liczb \(\displaystyle{ 1,2,\ldots , n+k}\) dokładnie \(\displaystyle{ n}\) należy do \(\displaystyle{ Y}\)
lub dokładnie \(\displaystyle{ n}\) z nich do niego nie należy. Funkcja ta jest w oczywisty sposób dobrze określona i tak dalej Prosto wykazać, że
moc rodziny \(\displaystyle{ f^{-1}(k)}\) wynosi \(\displaystyle{ 2^{n-k} {n+k \choose k}}\), ponieważ każdy zbiór \(\displaystyle{ Y''}\) z tej rodziny możemy rozpisać na
sumę dowolnego podzbioru zbioru \(\displaystyle{ S_{2n}\backslash S_{n+k+1}}\) (jest ich \(\displaystyle{ 2^{n-k-1}}\)) oraz \(\displaystyle{ k}\) lub \(\displaystyle{ n}\) - elementowego
podzbioru zbioru \(\displaystyle{ S_{n+k}}\) (liczba \(\displaystyle{ n+k+1}\) - o ile należy do \(\displaystyle{ X}\) - musi należeć do \(\displaystyle{ Y''}\) jeżeli
\(\displaystyle{ \overline{\overline{Y'' \cap S_{n+k}}}=n}\) oraz nie może należeć gdy \(\displaystyle{ \overline{\overline{Y'' \cap S_{n+k}}}=k}\) ). To oznacza,
że \(\displaystyle{ \overline{\overline{f^{-1}(k)}}=2^{n+k-1}{n+k\choose k}+2^{n+k-1}{n+k\choose n}=2^{n-k}{n+k\choose k}}\).
Podzbiory o innej postaci nie pozwolą nam uzyskać wartości \(\displaystyle{ k}\) dla funkcji \(\displaystyle{ f}\). Ponieważ zbiorem wartości funkcji \(\displaystyle{ f}\) jest zbiór \(\displaystyle{ \{0,1,\ldots,n\}}\) to liczba podzbiorów \(\displaystyle{ X}\) będzie równa \(\displaystyle{ 2^{2n}=\sum_{k=0}^n\overline{\overline{f^{-1}(k)}}=\sum_{k=0}^n 2^{n-k}{n+k\choose k}}\), co kończy dowód.
PS. Wybaczcie, że w kilku miejscach trochę zamachałem rękami, ale rozpisywanie tego dokładnie zajęłoby mi chyba z pół godziny
Wykażemy, że wyrażenie \(\displaystyle{ \sum_{i=0}^{n} 2 ^{n-i} {n+i \choose i}}\) jest równe liczbie podzbiorów zbioru \(\displaystyle{ X=\{1,2,\ldots,2n\}}\), czyli \(\displaystyle{ 2^{2n}}\).
Oznaczmy \(\displaystyle{ S_i=\{1, 2,\ldots,i\}}\). Niech funkcja \(\displaystyle{ f}\) każdemu podzbiorowi \(\displaystyle{ Y}\) zbioru \(\displaystyle{ X}\) przyporządkuje największy taki indeks
\(\displaystyle{ k\in\{0,1\ldots,n\}}\), że moc co najmniej jednego ze zbiorów \(\displaystyle{ Y \cap S_{n+k}}\) lub \(\displaystyle{ (S_{2n}\backslash Y) \cap S_{n+k}}\) wynosi
\(\displaystyle{ n}\). Mówiąc obrazowo, szukamy największego \(\displaystyle{ k\leq n}\) takiego, że spośród liczb \(\displaystyle{ 1,2,\ldots , n+k}\) dokładnie \(\displaystyle{ n}\) należy do \(\displaystyle{ Y}\)
lub dokładnie \(\displaystyle{ n}\) z nich do niego nie należy. Funkcja ta jest w oczywisty sposób dobrze określona i tak dalej Prosto wykazać, że
moc rodziny \(\displaystyle{ f^{-1}(k)}\) wynosi \(\displaystyle{ 2^{n-k} {n+k \choose k}}\), ponieważ każdy zbiór \(\displaystyle{ Y''}\) z tej rodziny możemy rozpisać na
sumę dowolnego podzbioru zbioru \(\displaystyle{ S_{2n}\backslash S_{n+k+1}}\) (jest ich \(\displaystyle{ 2^{n-k-1}}\)) oraz \(\displaystyle{ k}\) lub \(\displaystyle{ n}\) - elementowego
podzbioru zbioru \(\displaystyle{ S_{n+k}}\) (liczba \(\displaystyle{ n+k+1}\) - o ile należy do \(\displaystyle{ X}\) - musi należeć do \(\displaystyle{ Y''}\) jeżeli
\(\displaystyle{ \overline{\overline{Y'' \cap S_{n+k}}}=n}\) oraz nie może należeć gdy \(\displaystyle{ \overline{\overline{Y'' \cap S_{n+k}}}=k}\) ). To oznacza,
że \(\displaystyle{ \overline{\overline{f^{-1}(k)}}=2^{n+k-1}{n+k\choose k}+2^{n+k-1}{n+k\choose n}=2^{n-k}{n+k\choose k}}\).
Podzbiory o innej postaci nie pozwolą nam uzyskać wartości \(\displaystyle{ k}\) dla funkcji \(\displaystyle{ f}\). Ponieważ zbiorem wartości funkcji \(\displaystyle{ f}\) jest zbiór \(\displaystyle{ \{0,1,\ldots,n\}}\) to liczba podzbiorów \(\displaystyle{ X}\) będzie równa \(\displaystyle{ 2^{2n}=\sum_{k=0}^n\overline{\overline{f^{-1}(k)}}=\sum_{k=0}^n 2^{n-k}{n+k\choose k}}\), co kończy dowód.
PS. Wybaczcie, że w kilku miejscach trochę zamachałem rękami, ale rozpisywanie tego dokładnie zajęłoby mi chyba z pół godziny