Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Uzasadnij, udowodnij (nie kombinatorycznie)

Strona 1 z 1

[ Posty: 2 ]

Autor

Wiadomość

NataliaAnna Offline

Tytuł: Uzasadnij, udowodnij (nie kombinatorycznie)

Napisane: 6 sty 2018, o 17:15

Posty: 75
Lokalizacja: Wrocław

Mam duży problem z trzema zadaniami i próbowałam je rozgryźć na kilka sposobów, ale albo robię gdzieś błąd, albo po prostu mam złe podejście. Chodzi o przykłady poniżej, chce je uzasadnić lub udowodnić, ale nie kombinatorycznie.

$\sum_{n}^{k=1} {n \choose k} \frac{(-1) ^{k+1} }{k} = \sum_{n}^{k=1} \frac{1}{k}$
Myli mnie brak $k+1$ w mianowniku po lewej stronie, przez to nie mam pojęcia jak przez to przebrnąć.
$\sum_{n}^{k=2}k(k-1) {n \choose k} =n(n-1)2^{n-2}$
To próbowałam robić przez zwykłe wzory na sumy, jednak przez to, że $k=2$ , nie wychodziło mi to, co po lewej stronie, bo wzory działają dla $k=0$ lub $k=1$ .
$\sum_{l}^{k=0} {n \choose k} {m \choose l-k} = {m+n \choose l}$

Góra

Premislav Online

Tytuł: Uzasadnij, udowodnij (nie kombinatorycznie)

Napisane: 6 sty 2018, o 18:19

Posty: 13141
Lokalizacja: Wrocław

1)
Indukcja po $n$ , dla $n=1$ po obu stronach otrzymamy $1$ , zaś w drugim kroku indukcyjnym korzystamy z tożsamości ${n \choose k}+{n \choose k-1}={n+1 \choose k}, \ k\ge 1$
Czyli:
$\sum_{k=1}^{n+1} {n+1 \choose k} \frac{(-1) ^{k+1} }{k}=\\=\sum_{k=1}^{n} {n \choose k} \frac{(-1) ^{k+1} }{k} +\sum_{k=1}^{n} {n \choose k-1} \frac{(-1) ^{k+1} }{k}=[\text{ zał. indukcyjne}]=\\= \sum_{k=1}^{n}\frac 1 k+\frac{1}{n+1} \sum_{k=1}^{n}{n+1 \choose k}(-1)^{k+1}=\\= \sum_{k=1}^{n}\frac 1 k+\frac{1}{n+1}\left( 1- \sum_{k=0}^{n+1} {n+1\choose k}(-1)^k\right) =\\= \sum_{k=1}^{n}\frac 1 k+\frac{1}{n+1}\left( 1-\left( 1-1\right)^{n+1} \right)= \sum_{k=1}^{n+1}\frac 1 k$

2) Zauważ, że
$k(k-1){n \choose k}=n(n-1){n-2\choose k-2}$ dla $k=2,3\ldots n$
(można to policzyć, rozpisując na silnie i skracając)
oraz że
$\sum_{k=2}^{n} {n-2 \choose k-2}= \sum_{k=0}^{n-2} {n-2 \choose k}=2^{n-2}$

3) To jest trudniejsze, pomyślę chwilę.

-- 6 sty 2018, o 20:14 --

Dobra, gdyby ktoś szukał niekombinatorycznego dowodu (3.), to mnie to akurat przerosło, ale macie tutaj:
https://www.cut-the-knot.org/arithmetic ... tion.shtml
Dowód nr 4 jest całkiem prosty, nawet bardzo.

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 2 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
Wykazać kombinatorycznie, szufladkowanie Dirchileta	Smule	1
Pokazać kombinatorycznie, sumy	patry93	4
Udowodnij tożsamość kombinatoryczną	Krzysaker	0
Udowodnij istnienie - zadanie 2	Dario1	1
Udowodnij równanie - zadanie 14	kumpelka212	1

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]