\sum 2^{-k\cdot n} = \sum (2^{-n})^k = \frac 1 {1 - 2^{-n}} = \frac {2^{n}} {2^{n}-1}
S = \sum 2^{-k}
- \sum 2^{-k\cdot 2} - \sum 2^{-k\cdot 3} - \sum 2^{-k\cdot 5} - \sum 2^{-k\cdot 7}
+ \sum 2^{-k\cdot 2\cdot 3} + \sum 2^{-k\cdot 2\cdot 5} + \sum 2^{-k\cdot 2\cdot 7} + \sum 2^{-k\cdot 3\cdot 5} + \sum 2^{-k\cdot 3\cdot 7} + \sum 2^{-k\cdot 5\cdot 7}
- \sum 2^{-k\cdot 2 \cdot 3\cdot 5} - \sum 2^{-k\cdot 2 \cdot 3\cdot 7} - \sum 2^{-k\cdot 2 \cdot 5\cdot 7} - \sum 2^{-k\cdot 3 \cdot 5\cdot 7}
+ \sum 2^{-k\cdot 2 \cdot 3\cdot 5 \cdot 7}
= 2 - \frac 4 3 - \frac 8 7 - \frac {32} {31} - \frac {128} {127} + \frac {64} {63} + \frac {1024} {1023} + \frac {16384} {16383} + \frac {32768} {32767} + \dots \approx 0.5006
(gdyby chcieć policzyć to na palcach, można każdy z tych ułamków dla większych n przybliżyć jako 1)
Przypomnę notację: \Phi(a_n) oznacza funkcję tworzącą a_n.
\Phi(a_n) = A(x) = a_n x^n = a_0 + a_1 x^1 + a_2 x^2 + \dots
\displaystyle \Phi(a_{2n}) = a_0 + a_2 x^1 + a_4 x^2 + \dots = a_0 + a_2 x^{2/2} + a_4 x^{4/2} + \dots = \Phi(b_n)(x^{1/2}) = \frac {A(x^{1/2}) + A(-x^{1/2})} 2 , gdzie b_n = \cases{a_n & \text{n parzyste} \cr 0 & \text{otherwise}}.
\displaystyle \frac {A(x^{1/3}) + A(x^{1/3} \cdot (-1)^{2/3}) + A(x^{1/3} \cdot (-1)(-1)^{1/3})} {3} =
\displaystyle \frac {3 a_0 + (1 + (-1)^{2/3} + (-1)^{1/3})a_1 x^{1/3} + (1 + (-1)^{2/3} +(-1)^{1/3} )a_2 x^{2/3} + 3 a_3 x^1 + \dots} 3 = \frac {3a_0 + 3a_3x^1 + \dots} 3 = \Phi(a_{3n})
—
Troche komentarza do metody szukania „wybiórczych” ciągów. Oczywiście można strzelić i trafić, ale można do tego podejść również bardziej metodycznie. Zwłaszcza, że tutaj mamy równoodległe elementy, a być może nie chcemy, żeby tak było, czy coś tam.
Np. szukamy \Phi(a_{3n}), a mamy do dyspozycji \Phi(a_n) = A(x). Dotychczas wpadliśmy na dwa triki – dla \Phi(a_{2n}) oraz \Phi(a_{3n}). Obydwa były liniową kombinacją jakiejś aplikacji naszego oryginalnego A(x). Czyli:
\cases{ a(a_0 + \alpha a_1 x + \alpha^2 a_2 x^2 + \alpha^3 a_3 x^3 + \dots) \cr + b(a_0 + \beta a_1 x + \beta^2 a_2 x^2 + \beta^3 a^3 x^3 + \dots) \cr + c(a_0 + \gamma a_1 x + \gamma^2 a_2 x^2 + \gamma^3 a^3 x^3 + \dots) \cr = a_0 + a_3 x^3 + \dots }
Gdzie a,b,c to współczynniki kombinacji liniowej, a \alpha, \beta, \gamma to nasze szukane trikowe rzeczy które wstawiamy do A(x)
(x-ami można się zająć później)
To jeszcze nie jest takie fajne, bo mamy nieskończenie wiele termów. Ale możemy zauważyć, że wyrzucamy termy cyklicznie. To znaczy, że \alpha, \beta, \gamma muszą się cyklicznie zachowywać. A dokładniej muszą być takie same przy podniesieniu do co trzecich potęg. Można to osiągnąć przez dodanie warunków:
\cases{ \alpha^3 = 1 \cr \beta^3 = 1 \cr \gamma^3 = 1 \cr }
A to nam ogranicza możliwe rozwiązania do pierwiastków trzeciego stopnia liczby 1, czyli po pierwsze mamy skończoną liczbą możliwych rozwiązań (fajnie). Po drugie, możemy się zająć tylko pierwszymi trzema termami:
\cases{ a(a_0 + \alpha a_1 x + \alpha^2 a_2 x^2) \cr + b(a_0 + \beta a_1 x + \beta^2 a_2 x^2) \cr + c(a_0 + \gamma a_1 x + \gamma^2 a_2 x^2) \cr = a_0 }
Przekształcając:
\cases{ a + b + c = 1 \cr a \alpha + b \beta + c \gamma = 0 \cr a \alpha^2 + b \beta^2 + c \gamma^2 = 0 \cr }
Nie wiem jak się rozwiązuje takie układy równań, ale jako że mamy 3^3 potencjalnych rozwiązań, można w byle Haskellu sprawdzić wszystkie.
Oczywiście nie gwarantuję, że ta metoda jest poprawna ani kompletna. Być może jest jakiś warunek, którego tu brakuje, a który przeoczyłem.
\displaystyle ((1+x)^a)^{(n)} = a^{\underline n} (1+x)^{a-n}
\displaystyle (1+x)^a = \sum_{n=0}^{\infty} \frac 1 {n!} ((1+x)^a)^{(n)}(x_0) \cdot (x-x_0)^n = \sum_{n=0}^{\infty} \frac {a^{\underline n}} {n!} (1+x_0)^{a-n} \cdot (x-x_0)^n.
Dla x_0 = 0 mamy więc \displaystyle (1+x)^a = \sum_{n=0}^{\infty} \frac {a^{\underline n}} {n!} x^n
a)
\displaystyle F(x) = \sum_{n=0}^{\infty} a_n x^n = 1 + x + x^2 + \sum_{n=3}^{\infty} (a_{n-1} + a_{n-2} + a_{n-3} + 1) x^n =
1 + x + x^2 + x(F(x)-2) + x^2(F(x)-1) + x^3F(x) + \frac 1 {1-x} - 1 - x -x^2 = xF(x) -2x + x^2F(x) - x^2 + x^3F(x) + \frac 1 {1-x}
\displaystyle (1-x-x^2-x^3)F(x) = -2x-x^2+\frac 1 {1-x} = \frac {-2x + x^2 + x^3 + 1} {1-x}
A więc \displaystyle F(x) = \frac {-2x + x^2 + x^3 + 1} {(1-x)(1-x-x^2-x^3)}.
b)
\displaystyle F(x) = x + \sum_{n=2}^{\infty} (a_{n-1} + a_{n-2} + \frac 1 {n-1})x^n = xF(x) + x^2F(x) + \sum_{n=1}^{\infty} \frac 1 n x^{n+1} = xF(x) + x^2F(x) -\frac{x\log(1-x)}{1-x}
\displaystyle (1-x-x^2)F(x) = \frac{-x\log(1-x)}{1-x}
\displaystyle F(x) = \frac {-x\log(1-x)} {(1-x)(1-x-x^2)}
c)
\displaystyle F(x) = 1 + \sum_{n=1}^{\infty} (\sum_{k=0}^{n-1} a_{n-1-k} \frac 1 {k!}) x^n = 1 + \sum_{n=1}^{\infty} \sum_{k=0}^{n-1} a_{n-1-k} \frac 1 {k!} x^n = 1+ \sum_{n=1}^{\infty} \sum_{k=0}^{\infty} a_k \frac 1 {(n-1)!} x^{k+n} = 1 + \sum_{n=1}^{\infty} F(x) \frac 1 {(n-1)!} x^n = 1 + F(x) x e^x
\displaystyle F(x) = \frac 1 {1 - xe^x}
Później sprawdzę, czy zadanie jest zrobione dobrze (teraz jest późno).
\displaystyle P(x) = \prod_{k=1}^{\infty} \frac 1 {1-x^k}
\displaystyle R(x) = \prod_{k=1}^{\infty} (1+x^k)
\displaystyle R(x) P(x^2) = \prod_{k=1}^{\infty} \frac {1+x^k} {1-x^{2k}} = \prod_{k=1}^{\infty} \frac {(1+x^k)} {(1+x^k)(1-x^k)} = P(x)
\displaystyle {n \brack k} = (n-1) {n-1 \brack k} + {n-1 \brack k-1}.
Wyobraźmy sobie wszystkie sposoby na jakie można z permutacji n-1-elementowych uzyskać permutacje n-elementowe mające k rozłącznych cykli. Możemy to zrobić na dwa sposoby:
Teraz udowodnimy \displaystyle x^{\underline n} = \sum_{k=0}^{\infty} {n \brack k} x^k przez indukcję po n.
Dla n=1. \displaystyle x^{\underline 1} = x = 0 + x = {1 \brack 0} + {1 \brack 1}x. OK.
Dla n>1. \displaystyle \sum_{k=0}^{\infty} {n \brack k} x^k = \sum_{k=1}^{\infty} (n-1) {n-1 \brack k} x^k + \sum_{k=0}^{\infty} {n-1 \brack k-1} x^k = (n-1)x^{\underline {n-1}} + x \cdot x^{\underline {n-1}} = x^{\underline {n-1}} (x+n-1) = x^{\underline n}. OK.
\displaystyle \int_0^{\infty} G_e(zt)e^{-t} \; dt = \int_0^{\infty} (\sum_{n=0}^{\infty} a_n \frac{ z^nt^n} {n!} e^{-t}) \; dt = \sum_{n=0}^{\infty} a_n z^n \frac 1 {n!} (\int_0^{\infty} t^n e^{-t} \; dt) = \sum_{n=0}^{\infty} a_n z^n \frac {\Gamma(n+1)} {n!} = \sum_{n=0}^{\infty} a_n z^n \frac {n!} {n!} = \sum_{n=0}^{\infty} a_n z^n = G(z)