Matematické Fórum

Mihulik

Ahoj,
mám (bez použití indukce) dokázat tvrzení:
$\forall n\in N: \sum_{k=0}^{n} \binom{n}{k}2^k = 3^n$

Samozřejmě bych mohl říct, že se vlastně jedná o binomickou větu (kterou už jsme si dokazovali na přednášce), ale to asi nebude to, co chce cvičící vidět...

Pak mě napadla následující úvaha:
$\binom{n}{k}$ mohu interpretovat jako počet všech k-prvkových podmnožin n prvkové množiny a $2^k$ jako počet všech podmnožin k prvkové množiny.

Tedy sumu na levé straně mohu interpretovat jako počet všech podmnožin všech k prvkových (k jde od 1 do n) podmnožin n prvkové množiny (tato věta je zmatené a nejsem si jistej, jestli úplně přesně vyjadřuje to, co chci vyjádřit, ale nějak mě nenapadá lepší formulace...).

Mohu říct, že pokud označím X původní n prvkovou množinu, tak počet zobrazení z X do Y, kde Y je tří prvková množina je právě $3^n$
Problém je, že si nejsem jistej, jak tuto množinu Y definovat, abych všemi možnými zobrazeními z X do Y pokryl právě všechny případy, o kterých jsem mluvil v předešlé uvaze.

Myslím (intuitivně), že jsem na správné cestě a takto bych důkaz mohl vést.
Nemůžu ovšem přijít na to, jak ho "vybrousit" do konečné formální podoby.

Byl bych moc vděčný, kdyby mi někdo pomohl.:)

Děkuji!

FailED · 25. 10. 2011 22:27

Suma na levé straně vyjadřuje počet dvojic A,B t.ž. $A\subseteq B\subseteq X$ kde $|X|=n$ . Když si vezmeš funkci zobrazující X do Y={1,2,3} tak, že na 1 se zobrazí prvky, které nejsou v B, na 2 prvky, které jsou v B ale ne v A a na 3 prvky, které jsou v A, dostaneš co potřebuješ.

Mihulik · 25. 10. 2011 22:30

Přesně takový zápis jsem měl na papíře... zdá se, že to bude ono:)
Děkuji!

Matematické Fórum

#1 25. 10. 2011 21:47 — Editoval Mihulik (25. 10. 2011 21:49)

Důkaz rovnosti bez indukce

#2 25. 10. 2011 22:27

Re: Důkaz rovnosti bez indukce

#3 25. 10. 2011 22:30

Re: Důkaz rovnosti bez indukce

Zápatí