KÓŁECZKO Z BAJECZEK I REKURENCJI (24.01.07)

1. Udowodnić, że:

∑_{k=0}^{n} k ( \begin{matrix}n \\ k \end{matrix} ) = n2^{n−1}

2. Udowodnić, że:

∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) ^{2} = ( \begin{matrix}2n \\ n \end{matrix} )

3. Udowodnić, że:

∑_{k=0}^{n} k(k − 1) ( \begin{matrix}n \\ k \end{matrix} ) = n(n − 1)2^{n−2}

4. Udowodnić, że dla każego n − 1 k 1:

∑_{i=0}^{k} ( \begin{matrix}n \\ i \end{matrix} ) ( \begin{matrix}n − i \\ k − i \end{matrix} ) = 2^{k} ( \begin{matrix}n \\ k \end{matrix} )

5. Udowodnić, że:

∑_{a,b,c} ( \begin{matrix}n \\ a + b \end{matrix} ) ( \begin{matrix}n \\ b + c \end{matrix} ) ( \begin{matrix}n \\ c + a \end{matrix} ) = 2^{3n−2}

6. Ile jest prostok _{}atów w kratce N × N?

7. Na ile sposobów można pokryć pasek 2 × N kostkami domina 1 × 2?

8. Znaleźć wzory jawne rekurencji, jeśli a_{0} = 1, a_{1} = 3:

a) a_{n+1} = 3a_{n} + 4a_{n−1}

b) a_{n+1} = 4a_{n} + 2a_{n−1} + 3^{n} + 5

c) a_{n+1} = 7a_{n} − 16a_{n−1} + 12a_{n−2} dla a_{2} = 5

9. Żaba skacze po s _{}asiesnich wierzchołkach ośmik _{}ata foremnego. Zaczyna w A, gdy dotrze do naprzeciwległego wierzchołka (czyli E) zatrzymuje si_{}e na obiad (i już wi_{}ecej nie skaczce jak głupia). Na ile różnych sposobów może dotrzeć do wierzchołka E w dokładnie n ruchach?