Własność symbolu Newtona

[moss2]

\(\displaystyle{ k \in N \wedge n \in N \wedge k<n}\)

\(\displaystyle{ {n \choose k} + {n \choose k+1} = {n+1 \choose k+1}}\)

\(\displaystyle{ \frac{n!}{k!\cdot(n-k)!}+ \frac{n!}{(k+1)!\cdot(n-k-1)!}=\frac{(n+1)!}{(k+1)!\cdot(n-k)!}/:(n-k-1)!}\)

\(\displaystyle{ \frac{n!\cdot(n-k-1)!}{k!\cdot(n-k)!}+\frac{n!}{(k+1)!}=\frac{(n+1)!\cdot(n-k-1)!}{(k+1)!\cdot(n-k)!}}\)

\(\displaystyle{ \frac{n!}{k!\cdot(n-k)}+\frac{n!}{(k+1)!}=\frac{(n+1)!}{(k+1)!\cdot(n-k)}/\cdot(k+1)!}\)

\(\displaystyle{ \frac{n!\cdot(k+1)!}{k!\cdot(n-k)}+\frac{n!}{1}=\frac{(n+1)!}{(n-k)}}\)

\(\displaystyle{ \frac{n!\cdot(k+1)}{(n-k)}+\frac{n!}{1}=\frac{(n+1)!}{(n-k)}/\cdot(n-k)}\)

\(\displaystyle{ n!\cdot(k+1)+n!\cdot(n-k)=(n+1)!}\)

\(\displaystyle{ k+1+n-k=n+1}\)

\(\displaystyle{ k=k}\)

[Premislav]

Przekształcenia są poprawne, ale warto dopisać, iż są one równoważne (bo samo to, że wychodząc od tezy, doszedłeś do czegoś prawdziwego, nie wystarcza za dowód tezy).

-- 8 lip 2015, o 11:43 --

Istnieje też prosty dowód kombinatoryczny, opierający się na tym, ze przy założeniach jak u Ciebie \(\displaystyle{ {n \choose k}}\) to liczba \(\displaystyle{ k}\)-elementowych podzbiorów zbioru \(\displaystyle{ n}\)-elementowego.

[Poszukujaca]

Premislav, jak wygląda ten dowód algebraiczny?

[Premislav]

Poszukujaca, miałaś oczywiście na myśli kombinatoryczny. Z grubsza o tak:
przy założeniach jak w pierwszym poście z tego wątku \(\displaystyle{ {n+1 \choose k+1}}\) to liczba \(\displaystyle{ k+1}\)-elementowych podzbiorów zbioru \(\displaystyle{ n+1}\)-elementowego. Ustalmy dowolny element zbioru \(\displaystyle{ n+1}\)-elementowego i zauważmy, że możemy wybrać \(\displaystyle{ k+1}\) spośród \(\displaystyle{ n+1}\)elementów albo wybierając wśród nich ten jeden konkretny przez nas ustalony - a to się odbywa na \(\displaystyle{ {1 \choose 1}{n\choose k}}\) sposobów, albo pomijając ten ustalony element - tj. wybieramy \(\displaystyle{ k+1}\) spośród \(\displaystyle{ n}\) pozostałych.

[Poszukujaca]

Nie do końca rozumiem..

Jeśli mamy \(\displaystyle{ n+1}\) elementów zbioru i jeden z nich ustalimy jako element podzbioru \(\displaystyle{ k+1}\) elementowego, to tworząc podzbiory wybieramy już tylko \(\displaystyle{ k}\) elementów spośród \(\displaystyle{ n}\) elementów czyli mamy \(\displaystyle{ c_{n+1}^{1} \cdot c_{n}^{k} = {n+1 \choose 1} \cdot {n \choose k}}\)

[Medea 2]

To działa inaczej. Masz grupę \(\displaystyle{ n = 11}\) osób, z czego dziesięcioro to dzieci, a jedna to nauczycielka. Teraz wybierając \(\displaystyle{ k = 3}\) osoby (podgrupę) możesz to zrobić wybierając nauczycielkę i \(\displaystyle{ k - 1 = 2}\) dzieci lub \(\displaystyle{ k = 3}\) dzieci (bez nauczycielki); ewentualnie wybrać \(\displaystyle{ k = 3}\) osoby nie patrząc, kim one są.

[Poszukujaca]

Medea 2, dziękuję. Wspaniały przykład. Teraz już rozumiem jak działa ten wzór.

Miżna po prostu jeden z elementów zbioru wyróżnić i w ten sposób rozbić na dwa przypadki, których możliwości się sumują.

Zaciekawiło mnie to. Co się stanie, gdy wyróżnimy dwa elementy w zbiorze \(\displaystyle{ n+2}\) elementowym? Czy prawdziwy wtedy będzie wzór:
\(\displaystyle{ {n \choose k}+ {2 \choose 1} \cdot {n \choose k+1} + {n \choose k+2}={n+2 \choose k+2}}\)
Dochodzi tu przypadek, kiedy wybieramy jeden z elementów wyróżnionych i resztę niewyróżnionych.

[SlotaWoj]

@Premislav

Przekształcenia są poprawne, ale warto dopisać, iż są one równoważne (bo samo to, że wychodząc od tezy, doszedłeś do czegoś prawdziwego, nie wystarcza za dowód tezy).

Jeżeli z przekształceń wynika, że obie strony równania są równoważne, to czy trzeba czegoś więcej?

[Premislav]

Może uwaga o przekształceniach równoważnych to w przypadku przekształcania równości nadmiar pedantyzmu (właściwie jedyne, co mogłoby zaszkodzić równoważności przekształceń przy równaniu to chyba pomnożenie przez zero). Jakoś się przyzwyczaiłem do równań modularnych i nierówności, gdzie mogą się pojawić przejścia będące implikacjami, a nie równoważnościami i wtedy wychodzenie od tezy może prowadzić do błędu.
Racja, nie będę już pisać, bo same głupoty wychodzą.

[SlotaWoj]

@Premislav

1. Dziękuję za odpowiedź.
2. Nie potrzebnie się tak stresujesz. Po prostu wykazałeś się ostrożnością, a lepiej jest być ostrożnym, niż nieostrożnym.

[kerajs]

Czy prawdziwy wtedy będzie wzór:
\(\displaystyle{ {n \choose k}+ {2 \choose 1} \cdot {n \choose k+1} + {n \choose k+2}={n+2 \choose k+2}}\)
Dochodzi tu przypadek, kiedy wybieramy jeden z elementów wyróżnionych i resztę niewyróżnionych.

Prawdziwość tego, jak i napisanego w temacie, wzoru można błyskawicznie zweryfikować na trójkącie Pascala.

[Poszukujaca]

kerajs, rzeczywiście. Dziękuję.