2022 Pierwszy termin
Zadanie 1
Rozwiąż równanie rekurencyjne:
\( a_0 = 1 \)
\( a_n = \frac{1}{6}(n+1)(n+2) - \frac{1}{3} \sum_{\substack{0 \leq i,j < n,\\1 \leq i+j \leq n}} a_i a_j a_{n-i-j} \)
Wskazówka wakacyjna
Rozwiązanie
Po policzeniu kilku pierwszych wartości tej sumy, stawiamy tezę, że wartość tej sumy dla każdego \(n\) wynosi jeden. Dowodzimy tę tezę indukcją.
Zakładamy, że dla każdego \(n, a_n = 1\) (indukcja zupełna). Baza jest oczywista.
Musimy pokazać, że \(a_{n+1} = \frac{1}{6}(n+2)(n+3) - \frac{1}{3} \sum_{\substack{0 \leq i,j < n+1,\\1 \leq i+j \leq n+1}} a_i a_j a_{n+1-i-j}=1\). Zauważmy, że największy indeks ciągu \(a_n\), jaki pojawia się w tej sumie to \(n\). Z założenia każdy element tej sumy wynosi jeden, a więc jej wartość to liczba jej elementów. Policzymy tę liczbę analizując ile jest elementów dla \(i=0,1,...,n\). Innymi słowy, liczymy ile par \(i, j\) spełnia warunek pod sumą.
\(i=0\). Wtedy \(j\) przebiega \(n\) elementowy zakres \(1,...,n\).
\(i>0\). Wtedy \(j\) przebiega \(n+1-i+1\) elementowy zakres \(0,1,...,n-i+1\).
Wartość sumy w \(a_{n+1}\) to suma liczb elementów wszystkich zakresów: \(n+\frac{n+1+2}{2}n=\frac{n^2+5n}{2}\) (Dla \(i>0\) sumujemy ciąg arytmetyczny o wzorze \(n+2-i\)).
Wykonajmy teraz rachunki: \(a_{n+1}=\frac{1}{6}(n^2+5n+6) - \frac{1}{3}(\frac{n^2+5n}{2})=\frac{n^2+5n+6}{6}-\frac{n^2+5n}{6}=1\)
Zadanie 2
Podział liczby nazywamy binarnym, jeśli wszystkie jego składniki są potęgami dwójki, na przykład liczba 5 ma 4 podziały binarne: \(1+1+1+1+1\), \(1+1+1+2\), \(1+2+2\), \(1+4\).
Udowodnij, że dokładnie połowa spośród podziałów binarnych \(n \geq 2\) ma parzystą liczbę składników.