Matematické Fórum

Skrytý text:
Myšlenka je ta, že se pokusíme sumu nějak kombinatoricky interpretovat. To však půjde jen tehdy, pokud se v sumě budou vyskytovat pouze celá čísla. Jak už zde řekl kolega Honzc, vyzkoušíme-li sečíst sumu pro malá , napadne nás hypotéza, že by měl součet být . Mělo by tedy platit . Chceme, aby nalevo i napravo byla pouze celá čísla. Nejprve se napravo zbavíme ve jmenovateli toho . Jak to uděláme? No pokud běží od do , bylo dobré sumu přenásobit číslem , čímž napravo získáme , kde je pro vždy nezáporné, tedy je celé číslo. Teď tedy máme vztah .
Další problém spočívá v tom, že nalevo straší ve jmenovateli . Co s tím? Přenásobme tedy obě strany rovnice tímto výrazem, přičemž napravo tento výraz schovejme dovnitř sumy. Získáme toto:  .
Poslední věc, která by nám mohla napravo vadit, je ten jmenovatel . V čitateli vidíme výraz . Kdybychom tam měli místo toho , tak  by šlo interpretovat jako počet -členných variací z prvků, což je jistě celé číslo. Je tedy potřeba si v čitateli vytvořit . Toho dosáhneme snadno tak, že obě strany rovnice vynásobíme číslem . Dostaneme tedy . Nalevo i napravo vystupují nyní pouze celá čísla, a tutíž půjde kombinatorická interpretace použít. A to už nechám na vás!

Skrytý text:
Důkaz navazuje na můj hint v příspěvku #4. Tam jsem dokázal, že dokazovaná rovnost je ekvivalentní s tím, že dokážeme . Taky jsem řekl, že idea celého důkazu je úlohu nějak kombinatoricky interpretovat - aneb použít metodu dvojího počítání. Výraz se dá interpretovat jako počet možných hesel, které jsou tvořeny znaky, přičemž každý znak je vybrán z možností. U hesla samozřejmě platí, že znaky se mohou opakovat a na pořadí záleží - tj. jsou to variace s opakováním. Pokud máme v hesle znaků a znaky vybíráme z nějaké n-prvkové množiny, tak z Dirichletova principu je jasné, že aspoň jeden znak bude v heslu aspoň dvakrát. To by nám mohlo napovědět, jak sumu napravo interpretovat. Víme, že v hesle se nějaký znak určitě zopakuje. Rozčleníme tedy hesla do kategorií podle toho, na kolikátém písmenu se poprvé nějaký znak zopakuje. Nechť prvních znaků je různých a potom -tý znak se vybere z těch znaků, které už byly použity. Kolik takových hesel s touto podmínkou existuje? Zjevně prvních znaků se nesmí opakovat a vybírám je z možností - jedná se o -členné variace (bez opakování) z prvků. Těch je celkem . Potom -tý znak musím vybrat z těch znaků, které už jsem použil - mám zjevně možností. No a nakonec mi zbývá dovybrat zbylých znaků, na které už nekladu žádnou podmínku - možností je tedy . Podle kombinatorického pravidla součinu je tedy celkem možností . Takže existuje právě hesel takových, že první opakující se znak je právě na -té pozici. První opakující se znak je buďto na 2. pozici, nebo na 3. pozici, ..., nebo na -té pozici. Žádná jiná možnost není. Proto vysčítáním výrazů pro dostanu nutně všechna možná hesla. Proto platí , což jsme chtěli dokázat.