\input dmmac

\serie4

\task
Nech� $n,k\in\N$, $k\le n$. Doka�te (nap��klad indukc�) n�sleduj�c� vzorec:
$$
{k\choose k}+{k+1\choose k}+{k+2\choose k}+\dots+{n\choose k} = {n+1\choose k+1}
$$
\body3

\task Kolik je v�ech neklesaj�c�ch funkc� $f\: [n]\to[m]$?
\body3

\task
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\in\N$ plat� $f(n)\le F_n \le g(n)$ (co�
pochopiteln� doka�te).
\body4


\bye

