Matematické Fórum

Tomas5 · 10. 02. 2016 14:41

Dokažte, že platí: $\sum_{k=0}^{n}{n+k\choose 2k}=F_{2n+1}$ .

Tomas5 · 24. 02. 2016 12:07

Nápověda:
Platí: $\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}{n-k\choose k}=F_{n+1}$

Andrejka3 · 25. 02. 2016 09:43

↑ Tomas5:
Ahoj. S tou nápovědou už jo..:

Autor skryl část textu. Zobrazit/skrýt!

Akorát by mě zajímalo, z čeho plyne nápověda.

Honzc · 25. 02. 2016 09:56 — Editoval Honzc (25. 02. 2016 10:01)

↑ Tomas5:
Nápovědou jsi podle mne moc nepomohl, protože to by se muselo také dokázat.
Vím, že to není důkaz, ale podívej se na obrázek.

Autor skryl část textu. Zobrazit/skrýt!

Pavel · 25. 02. 2016 10:07

↑ Tomas5:

Bez nápovědy:

Autor skryl část textu. Zobrazit/skrýt!

Anonymystik

↑ Tomas5: Kolika způsoby mohu vystoupat schodiště, pokud při jednom kroku se posunu nahoru buď o jeden schod, nebo o dva schody? Označme počet těchto způsobů $a_{n}$ Počet těchto způsobů vyjádřím dvěma způsoby:

1) Rozdělím si všechny způsoby na dvě disjunktní podmnožiny. Buď posledním krokem mé cesty bude posun o jeden schod, nebo posun o dva schody. Pokud poslední krok mé cesty byl posun o jeden schod, pak jsem předtím měl $a_{n-1}$ možností, jak se dostat na jeden schod před koncem. Pokud poslední krok mé cesty byl posun o dva schody, pak jsem předtím měl $a_{n-2}$ možností, jak se dostat na druhý schod před koncem. Celkový počet způsobů, jak cestu provést, je $a_{n} = a_{n-2} + a_{n-1}$ . Je zjevné, že $a_{1} = 1, a_{2} = 2$ . Rekurentní závislost a počáteční podmínka ukazuje, že posloupnost $a_n$ je vlastně posunutá Fibbonacciho posloupnost - tedy $a_n = F_{n+1}$ . Proto $a_{2n} = F_{2n+1}$ .

2) Uvažme tentokrát, že schodiště má délku $2n$ . Cestu přes schodiště si rozdělím opět na disjunktní podmnožiny, podle toho, kolik jsem na cestě udělal kroků po dvou schodech. Předpokládejme, že jsem jich udělal právě $k$ . Pak zbylý počet schodů je $2n-2k$ , které jsem přešel kroky, kde jsem se posunoval jen o jeden schod. Udělal jsem tedy celkem $(2n-2k)+k = 2n-k$ kroků, z čehož jich $k$ bylo po dvou schodech, zbytek po jednom schodě. To šlo provést právě $\binom{2n-k}{k}$ způsoby. Nyní musíme posčítat všechny disjunktní podmnožiny, tj. sčítat před všechna vhodná $k$ . Přitom zjevně $0 \leq k \leq n$ . Celkový počet je tedy $a_{2n} = \sum_{k=0}^{n} \binom{2n-k}{k}$ .

Srovnáním $a_{2n} = F_{2n+1} = \sum_{k=0}^{n} \binom{2n-k}{k}$ . Nahrazením $2n \to n$ jsem dokázal, že platí nápověda.