====== Matematyka Dyskretna (M) - Lista 7. ====== ===== Zadanie 1. ===== ===== Zadanie 2. ===== Dla $n=0, n=1$ trywialnie zachodzi. Dla $n>1$: $\displaystyle F_{n+2} = F_{n+1} + F_{n} = \sum_{i=0}^n {n-i \choose i} + \sum_{i=0}^{n-1} {n-i-1 \choose i} = \sum_{i=0}^n {n-i \choose i} + \sum_{i=1}^{n} {n-i \choose i-1} = {n \choose 0} + \sum_{i=1}^n {n-i \choose i} + \sum_{i=1}^{n} {n-i \choose i-1} = {0 \choose n+1} + {n+1 \choose 0} + \sum_{i=1}^n {n-i+1 \choose i} = \sum_{i=0}^{n+1} {n-i+1 \choose i}$ ===== Zadanie 3. ===== ${0 \choose 0}F_m = F_m$. ${1 \choose 0}F_m + {1 \choose 1}F_{m+1} = F_{m+2}$ ${2 \choose 0}F_m + {2 \choose 1}F_{m+1} + {2 \choose 2}F_{m+2} = F_m + F_{m+1} + F_{m+1} + F_{m+2} = F_{m+4}$. Wygląda na to, że $\sum_{i=0}^n {n \choose i} F_{m+i} = F_{m+2n}$. Sprawdziłem na przypadków bazowych, teraz sprawdzę dla kroku. $\displaystyle \sum_{i=0}^n {n \choose i} F_{m+i} = \sum_{i=0}^n {n-1 \choose i} F_{m+i} + \sum_{i=0}^n {n-1 \choose i-1} F_{m+i} = \sum_{i=0}^{n-1} {n-1 \choose i} F_{m+i} + \sum_{i=0}^{n-1} {n-1 \choose i} F_{m+i+1} = F_{m+2n-2} + F_{m+2n-1} = F_{m+2n}$ ===== Zadanie 4. ===== ===== Zadanie 5. ===== ===== Zadanie 6. ===== $a_0 = 1, a_1 = 0, a_n = \frac 1 2a_{n-1} + \frac 1 2a_{n-2}$ $a_{n+2} - \frac 1 2 a_{n+1} - \frac 1 2 a_n = 0$. Układamy anihilator $E^2 - \frac 1 2 E - \frac 1 2 = (E - 1)(E + \frac 1 2)$. Więc postać zwarta to $a_n = \alpha + \beta (-\frac 1 2)^n$. Wyliczmy stałe. $1 = a_0 = \alpha + \beta$ $0 = a_1 = \alpha + -\frac 1 2\beta$. Więc $\alpha = \frac 1 3, \beta = \frac 2 3$. Zatem $a_n = \frac 1 3 + \frac 2 3 (- \frac 1 2)^n$ ===== Zadanie 7. ===== **a)** $a_0 = a_1 = 0; \; a_{n+2} = 2a_{n+1} - a_n + 3^n - 1$ $a_{n+2} - 2a_{n+1} + a_n - 3^n + 1 = 0$. Do homogenicznej części wyrażenia anihilatorem będzie $E^2 - 2E + 1 = (E-1)^2$. Po zanihilowaniu zostanie ciąg $<3^n - 1>$, który z kolei można zaniholować przez $(E - 3)(E - 1)$. Zatem cały anihilator to $(E-1)^3(E-3)$. Więc $a_n$ ma postać $\alpha + \beta n + \gamma n^2 + \delta 3^n$. Policzmy stałe. $\cases{0 = a_0 = \alpha + \delta \cr 0 = a_1 = \alpha + \beta + \gamma + 3 \delta \cr 0 = a_2 = \alpha + 2 \beta + 4 \gamma + 9 \delta \cr 2 = a_3 = \alpha + 3 \beta + 9 \gamma + 27 \delta}$ Układ ten ma jedno rozwiązanie $\alpha = -\frac 1 4; \beta = 0; \gamma = - \frac 1 2; \delta = \frac 1 4$. Zatem $a_n = - \frac 1 4 - \frac 1 2 n^2 + \frac 1 4 3^n$. **b)** $a_{n+2} - 4a_{n+1} + 4a_n - n2^{n+1} = 0$. Dla homogenicznej części równania anihilatorem będzie $E^2 - 4E + 4 = (E - 2)^2$. Dla drugiej części również będzie $(E-2)^2$, ostatecznym anihilatorem będzie więc $(E-2)^4$. Ogólna postać $a_n$ to $(\alpha + \beta n + \gamma n^2 + \delta n^3)2^n$ **c)** $a_{n+2} + a_{n+1} + a_n - 2^{n+1} = 0$. Anihilatorem będzie $(E^2 + E + 1)(E-2) = (E+(-1)^{1/3})(E-(-1)^{2/3})(E-2)$. Wychodziłoby na to, że postać ogólna $a_n$ to $\alpha (-1)^n(-1)^{n/3} + \beta (-1)^{2n/3} + \gamma 2^n$, ale nie jestem pewien czy można stosować anihilatory do ciągów zespolonych. ===== Zadanie 8. ===== $a_{n+3} - a_n = 0$. Anihilatorem będzie $E^3 - 1 = (E - 1)(E + (-1)^{1/3})(E - (-1)^{2/3})$. Czyli $a_n = \alpha + \beta(-1)^n(-1)^{n/3} + \gamma (-1)^{2n/3}$. Przyjmując $a_0 = 0, a_1 = 1, a_2 = 2$ otrzymujemy układ: $\cases{ 0 = \alpha + \beta + \gamma \cr 1 = \alpha - (-1)^{1/3} \beta + (-1)^{2/3} \gamma \cr 2 = \alpha + (-1)^{2/3} \beta - (-1)^{1/3} \gamma}$ Co daje nam $\alpha = -3/(x^2-x-2) ; \beta = (2x-1)/(-x^2-2x-1); \gamma = 1/(x^2-2x)$, gdzie $x = (-1)^{1/3}$. Później może skończe to zadanie, ale $\lfloor \frac n 3 \rfloor = \frac {n - n \mathop{mod} 3} 3 $ ===== Zadanie 9. ===== Niech $a_n$ oznacza liczbę ciągów n liter zawierających parzystą liczbę wystąpień a. $a_1 = 25$. $a_n = 26^{n-1}-a_{n-1} + 25a_{n-1}$ $a_{n+1} - 24a_n - 26^{n-1}$. Anihilatorem będzie $(E - 24)(E-26)$. Postacią ogólną $a_n$ będzie więc $\alpha 24^n + \beta 26^n$. Rozwiążmy. $\cases{ 25 = 24 \alpha + 26 \beta \cr 626 = 576 \alpha + 676 \beta}$ Jedynym rozwiązaniem jest $\alpha = 1/2; \beta = 1/2$. Zatem $a_n = \frac 1 2 24^n + \frac 1 2 26^n$. Sprawdziłem w Haskielu, dobry wynik. ===== Zadanie 10. ===== $s_{n+1} - s_n - n2^n = 0$. Anihilator to $(E-1)(E-2)^2$. $s_n = \alpha + \beta 2^n + \gamma n 2^n$. $\cases{ 2 = s_1 = \alpha + 2\beta + 2\gamma \cr 10 = s_2 = \alpha + 4\beta + 8\gamma \cr 34 = s_3 = \alpha + 8\beta + 24\gamma } $. Jedynym rozwiązaniem układu jest $\alpha = 2; \beta = -2; \gamma = 2$. Zatem $s_n = 2 + (n-1)2^{n+1}$ ===== Zadanie 11. ===== Niech $d^0_n, d^1_n, d^2_n$ oznaczają liczbę poprawnych ciągów o długości n zakończonych na kolejno 0, 1 i 2. $d^0_n = d^0_{n-1} + d^1_{n-1} + d^2_{n-1}$ $d^1_n = d^0_{n-1} + d^2_{n-1}$ $d^2_n = d^0_{n-1} + d^1_{n-1}$ $c_n = d^0_n + d^1_n + d^2_n = 3d^0_{n-1} + 2d^0_{n-1} + 2d^2_{n-1} = 2c_{n-1} + d^0_{n-1} = 2c_{n-1} + c_{n-2}$. Anihilator to $E^2 - 2E - 1 = (E-1-\sqrt{2})(E-1+\sqrt{2})$. Więc $c_n$ ma postać $\alpha(1+\sqrt{2})^n + \beta (1-\sqrt{2})^n$. $\cases{3 = c_1 = (1+\sqrt{2})\alpha + (1-\sqrt{2})\beta\cr 7 = c_2 = (3+2\sqrt{2})\alpha + (3 - 2\sqrt{2}) \beta}$ $\alpha = \frac {1 + \sqrt{2}} {2}; \beta = \frac {1 - \sqrt{2}} {2}$. Zatem $c_n = \frac {1 + \sqrt{2}} {2} (1+\sqrt{2})^n + \frac {1 - \sqrt{2}} {2} (1-\sqrt{2})^n$. ===== Zadanie 12. ===== **a)** Zapiszmy wyrażenie jako $a_n = a_{n-1} + (n-1)n2^n$. Dla niego anihilator to $(E-1)(E-2)^3$. Więc $a_n = \alpha + \beta 2^n + \gamma n 2^n + \delta n^2 2^n$. $\cases{ 0 = a_1 = \alpha + 2 \beta + 2 \gamma + 2 \delta \cr 8 = a_2 = \alpha + 4 \beta + 8 \gamma + 16 \delta \cr 56 = a_3 = \alpha + 8 \beta + 24 \gamma + 72 \delta \cr 248 = a_4 = \alpha + 16 \beta + 64 \gamma + 256 \delta}$ Zatem $a = -8, b = 8, c = -6, d = 2$, a $a_n = -8 + (n^2 - 3n + 4) 2^{n+1} $ **b)** Zapiszmy wyrażenie jako $a_n = a_{n-1} + n^2 (-1)^n$. Anihilator $(E - 1)(E + 1)^3$. Zatem $a_n = \alpha + \beta (-1)^n + \gamma n (-1)^n + \delta n^2 (-1)^n$. $\cases{ -1 = a_1 = \alpha - \beta - \gamma - \delta \cr 3 = a_2 = \alpha + \beta + 2 \gamma + 4 \delta \cr -6 = a_3 = \alpha - \beta - 3 \gamma - 9 \delta \cr 10 = a_4 = \alpha + \beta + 4 \gamma + 16 \delta }$ Jedynym rozwiązaniem układu jest $\displaystyle \alpha = 0, \beta = 0, \gamma = 1/2, \delta = 1/2$. Zatem $a_n = \frac 1 2 { (n^2 + n) (-1)^n }$. **c)** Po pierwsze zauważmy, że $\displaystyle \frac 1 {(k+1)(k+2)(k+3)} = \frac 1 {2(k+1)} - \frac 2 {2(k+2)} + \frac 1 {2(k+3)}$, co można łatwo sprawdzić. $\displaystyle \sum_{k=1}^n \frac 1 {(k+1)(k+2)(k+3)} = \frac 1 {2\cdot 3\cdot 4} + \frac 1 {3\cdot 4\cdot 5} + \cdots + \frac 1 {n(n+1)(n+2)} + \frac 1 {(n+1)(n+2)(n+3)} = $ $\displaystyle = \frac 1 {2\cdot 2} - \frac 1 {2\cdot 3} - ( \frac 1 {2\cdot 3} - \frac 1 {2\cdot4} ) + \frac 1 {2\cdot 3} - \frac 1 {2\cdot 4} - ( \frac 1 {2\cdot 4} - \frac 1 {2\cdot5} ) + \cdots + \frac 1 {2n} - \frac 1 {2(n+1)} - ( \frac 1 {2(n+1)} - \frac 1 {2(n+2)} ) + \frac 1 {2(n+1)} - \frac 1 {2(n+2)} - ( \frac 1 {2(n+2)} - \frac 1 {2(n+3)} ) = \frac 1 4 - \frac 1 6 - \frac 1 {2(n+2)} + \frac 1 {2(n+3)}$ ===== Zadanie 13. ===== **a)** $b_n = na_n$ $\displaystyle B(x) = \sum_{n=0}^{\infty} n a_n x^n$ $\displaystyle A(x) = \sum_{n=0}^{\infty} a_n x^n$ $\displaystyle A(x)' = \sum_{n=0}^{\infty} (a_n x^n)' = \sum_{n=0}^{\infty} n a_n x^{n-1}$ $\displaystyle x A(x)' = \sum_{n=0}^{\infty} n a_n x^{n} = B(x)$ **b)** $c_n = a_n / n$ $\displaystyle C(x) = \sum_{n=1}^{\infty} a_n \frac {x^n} n = \sum_{n=1}^{\infty} a_n (\int_0^x x^{n-1} \; dx) = \int_0^x ( \sum_{n=1}^{\infty} a_n x^{n-1} ) \; dx = \int_0^x \frac { A(x) - A(0) } x \; dx$ **c)** $s_n = \sum_{k=0}^n a_k = \sum_{k=0}^n a_k j_{n-k}$, gdzie $j_k = 1$. więc $\displaystyle S(x) = \sum_{n=0}^{\infty} (\sum_{k=0}^n a_k j_{n-k}) x^n = \sum_{n=0}^{\infty} a_n x^n \cdot \sum_{n=0}^{\infty} j_n x^n = A(x) \cdot J(x) = \frac {A(x)} {1 - x}$ **d)** $d_n = \cases{a_n & n = 2k \cr 0 & n = 2k+1}$ $\displaystyle 2\cdot D(x) = 2a_0 + 2a_2 x^2 + 2a_4 x^4 + ... = (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + ...) + (a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 \pm ...) = A(x) + A(-x)$ więc $\displaystyle D(x) = \frac {A(x) + A(-x)} 2$ ===== Zadanie 14. ===== **a) oraz b)** Używamy wzoru z 13 a): $\displaystyle \sum_{n=0}^{\infty} n x^n = x (\sum_{n=0}^{\infty} x^n)' = x (\frac 1 {1 - x})' = \frac x {(1-x)^2}$ $\displaystyle \sum_{n=0}^{\infty} n^2 x^n = x (\sum_{n=0}^{\infty} n x^n)' = x (\frac x {(1-x)^2})' = \frac {x(x+1)} {(1-x)^3}$ $\displaystyle \sum_{n=0}^{\infty} n^3 x^n = x (\sum_{n=0}^{\infty} n^2 x^n)' = x (\frac {x(x+1)} {(1-x)^3})' = \frac {-x(x^2 + 4x +1)} {(1-x)^4}$ **c)** Twierdzę, że $\displaystyle A_k(x) = \frac 1 {(1-x)^{k+1}}$. Dowód będzie indukcją po $k$. Dla $k = 0$ jest $a_n = {n \choose 0} = 1$, więc wzór zachodzi. Dla $k>0$: Z wzoru rekurencyjnego na wartość symbolu Newtona wiemy, że ${n+k \choose k} = {n+k-1 \choose k} + {n+k-1 \choose k-1}$. $\displaystyle A_k(x) = \sum_{n=0}^{\infty} {n+k \choose k} x^n = \sum_{n=0}^{\infty} {n+k-1 \choose k} x^n + \sum_{n=0}^{\infty} {n+k-1 \choose k-1} x^n = x \sum_{n=0}^{\infty} {n+k-1 \choose k} x^{n-1} + A_{k-1}(x) = x x^{-1}{k-1 \choose k} + x \sum_{n=1}^{\infty} {n+k-1 \choose k} x^{n-1} + A_{k-1}(x) = x \sum_{n=0}^{\infty} {n+k \choose k} x^n + A_{k-1}(x) = x \cdot A_k(x) + A_{k-1}(x)$ $\displaystyle A_k(x) (1-x) = A_{k-1}(x)$ $\displaystyle A_k(x) = \frac {A_{k-1}(x)} {1-x} = \frac {1} {(1-x)(1-x)^{k}} = \frac {1} {(1-x)^{k+1}} $ ===== Zadanie 15. ===== **a)** Po pierwsze, $\displaystyle \log\frac{1+x}{1-x} = \log(1+x) - \log(1-x) = (-x - \frac{x^2} 2 - \frac{x^3} 3 - \dots) - (x - \frac{x^2} 2 + \frac{x^3} 3 \pm \dots) = 2x + 2\frac{x^3} 3 + 2\frac{x^5} 5 + \dots$ $\displaystyle A(x) = \sum_{k=0}^{\infty} (2k x^{2k} + \frac {x^{2k+1}} {2k+1}) = \sum_{k=0}^{\infty} 2k x^{2k} + \sum_{k=0}^{\infty} \frac {x^{2k+1}} {2k+1} = \frac x {2(1-x)^2} + \frac {-x} {2(1+x)^2} + \frac 1 2 \log \frac {1+x} {1-x}$ **b)** Niech $\Phi(a_n)$ oznacza funkcje tworzącą dla danego ciągu podanego w postaci zwartej. $\displaystyle \Phi(H_n) = \Phi(1 + 1/2 + 1/3 + \dots + 1/n) = \frac {\Phi(1/n)} {1-x} = \frac {\int_0^x \frac {\frac {1} {1-x} - 1}{x} \; dx} {1-x} = \frac {\int_0^x \frac {1} {1-x} \; dx} {1-x} = \frac {-\log(1-x)} {1-x}$