\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}^2 = {2n \choose n}}\)
Oczywisty jest pierwszy krok indukcyjny, dla n=0 wychodzi jeden. Ale jak to rozpisać dla \(\displaystyle{ \sum_{k=0}^{n+1} {n+1 \choose k}^2 = {2(n+1) \choose n+1}}\) ?
Dowód indukcyjny sumy kwadratów dwumianu Newtona
-
adamkowallo
- Użytkownik
- Posty: 2
- Rejestracja: 19 paź 2014, o 17:30
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
-
adamkowallo
- Użytkownik
- Posty: 2
- Rejestracja: 19 paź 2014, o 17:30
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Dowód indukcyjny sumy kwadratów dwumianu Newtona
Dowodzenie tego indukcyjnie to jest zbrodnia szydząca, gdy głos cierpień kwili.
Po bitwie pod Bielasicą w 1014 roku (albo parę lat później, nie pamiętam) Bazyli Bułgarobójca oślepił co drugiego z pojmanych wojowników cara bułgarskiego (tak naprawdę to chyba więcej z nich oślepił, ale to fajniej pasuje do treści zadania). Powiedzmy, że było \(\displaystyle{ 2n}\) jeńców i zastanówmy się, na ile sposobów można by wybrać tych do oślepienia. No to odpowiada na to standardowy wzorek po prawej, ale można do tego podejść trochę inaczej: dzielimy tych jeńców na dwie równoliczne grupy i z jednej oślepiamy \(\displaystyle{ k}\), a z drugiej \(\displaystyle{ n-k}\), co łącznie da \(\displaystyle{ n}\) oślepionych, dla \(\displaystyle{ k}\) od zera (oślepiamy wszystkich z pierwszej i żadnego z drugiej) do \(\displaystyle{ k=n}\) (oślepiamy wszystkich z drugiej, a ci z pierwszej mają szczęście w nieszczęściu).
Jak ktoś się upiera przy dowodzie indukcyjnym, to może przyda się fakt, że \(\displaystyle{ {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}}\), ale tak szczerze, to nie widzę prostego dowodu za pomocą indukcji.
Po bitwie pod Bielasicą w 1014 roku (albo parę lat później, nie pamiętam) Bazyli Bułgarobójca oślepił co drugiego z pojmanych wojowników cara bułgarskiego (tak naprawdę to chyba więcej z nich oślepił, ale to fajniej pasuje do treści zadania). Powiedzmy, że było \(\displaystyle{ 2n}\) jeńców i zastanówmy się, na ile sposobów można by wybrać tych do oślepienia. No to odpowiada na to standardowy wzorek po prawej, ale można do tego podejść trochę inaczej: dzielimy tych jeńców na dwie równoliczne grupy i z jednej oślepiamy \(\displaystyle{ k}\), a z drugiej \(\displaystyle{ n-k}\), co łącznie da \(\displaystyle{ n}\) oślepionych, dla \(\displaystyle{ k}\) od zera (oślepiamy wszystkich z pierwszej i żadnego z drugiej) do \(\displaystyle{ k=n}\) (oślepiamy wszystkich z drugiej, a ci z pierwszej mają szczęście w nieszczęściu).
Jak ktoś się upiera przy dowodzie indukcyjnym, to może przyda się fakt, że \(\displaystyle{ {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}}\), ale tak szczerze, to nie widzę prostego dowodu za pomocą indukcji.