The Postal Owl

1. Označíme si 	částečný součet $c_n =\sum^n_{k=0} \binom{n}{k}^2$

	To rozložíme jako $a_i = \binom{n}{i}, b_{n-i} = \binom{n}{i} = \binom{n}{n-i}$ 

	Takže $a_i = b_i$ a $c_n = \sum^n_{k=0} a_k \cdot b_{n-k}$

	Vytvořující funkce obou posloupnosti $(a_n)$ je $a(x) = \sum_{k=0}^n \binom{n}{k}x^k$, 

    což je základní vytvořující funkce $(x+1)^n$

	Pak $c(x) = (x+1)^2n = \sum_{k=0}^{2n} \binom{2n}{k} x^k$ 

    Teď se stačí podívat na koeficient u $x^n$, což je $\binom{2n}{n}$	



2. Platí $\sum^n_{k=0} k \binom{n}{k} = \sum^n_{k=0} (n-k) \binom{n}{k}$

	$2\sum^n_{k=0} k \binom{n}{k} = \sum^n_{k=0} n \cdot \binom{n}{k} = n \sum^n_{k=0} \binom{n}{k}$

	Ale $\sum^n_{k=0} \binom{n}{k}1^k1^{n-k}= (1+1)^n$

	Úpravou $\sum^n_{k=0} k \binom{n}{k} = n2^{n-1}$

Tak dvojka prý neprojde bez vytv. funkcí (...), takže přikládám jiné řešení:

Pro součet binomických koeficientů máme následující funkci $\sum^n_{k=0} \binom{n}{k} x^k = (x+1)^n$

Chtěli bychom do sumy dostat $k$. Když se podíváme na tabulku s pravidly pro práci s vytv. funkcemi, vidíme, že k tomu můžeme použít derivaci:

$\sum^n_{k=0} k \binom{n}{k} x^k = n(x+1)^{n-1}$.

Abychom se zbavili $x$ v součtu, dosadíme za něj jednotku:


$\sum^n_{k=0} k \binom{n}{k} 1^k = n(1+1)^{n-1}$.



$\sum^n_{k=0} k \cdot \binom{n}{k}= n2^{n-1}$.