Úkoly z diskrétní matematiky, 4. série

Veškerá tvrzení precizně zdůvodněte.

(4.1) Nechť n, k ∈ ℕ, k ≤ n. Dokažte (například indukcí) následující vzorec:

\binom{k}{k} + \binom{k + 1}{k} + \binom{k + 2}{k} + ⋯ + \binom{n}{k} = \binom{n + 1}{k + 1}

3 body

(4.2) Kolik je všech neklesajících funkcí f: [n] → [m]? 3 body (4.3) Dokažte, že Fibonacciho čísla F_{n} rostou exponenciálně. Tj. najděte vhodné

exponenciální funkce f a g takové, že pro každé n ∈ ℕ platí f(n) ≤ F_{n} ≤ g(n) (což pochopitelně dokažte). 4 body