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}
{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}
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
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.
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
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.
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}
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.
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)}
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
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}}
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}