From 702cfce575b3e5398648fce5e623a7db977850ee 2017-06-14 12:59:42
From: Tom Bannink <tom.bannink@cwi.nl>
Date: 2017-06-14 12:59:42
Subject: [PATCH] Add a^{(n)}_k formula for n=4,5

---

diff --git a/main.tex b/main.tex
index 5476939feffff07cee3e0e02715965e2839e0521..abd3cde6df99068eb8c35021caca298e0c8427c9 100644
--- a/main.tex
+++ b/main.tex
@@ -185,6 +185,17 @@
     \end{align*}
     For $n=3$ the system becomes very simple because regardless of the current state, the probability of going to $111$ is always equal to $(1-p)^3$. Therefore the expected number of resamplings is simply the expectation of a geometric distribution. This gives the formula for $R^{(3)}(p)$ as shown above. Note that the $k$-th coefficient of the powerseries of a function $f(p)$ is given by $\frac{1}{k!}\left.\frac{d^k f}{dp^k}\right|_{p=0}$, i.e. the $k$-th derivative to $p$ evaluated at $0$ divided by $k!$. For the function $R^{(3)}(p) = (1-p)^{-3} - 1$ this yields $a^{(3)}_k = (k+2)(k+1)/6$ for $k\geq 1$ and $a^{(3)}_0=0$.
 
+    We can do the same for $n=4,5$, which gives, for $k\geq 1$ (with Mathematica):
+    \begin{align*}
+        a^{(3)}_k &= \frac{(k+2)(k+1)}{6}\\
+        a^{(4)}_k &= \frac{1}{6}\left(2+\frac{(k+3)(k+2)(k+1)}{6}\right)\\
+        a^{(5)}_k &= \frac{1}{15}\left(\frac{(k+4)(k+3)(k+2)(k+1)}{20} - \frac{(k+3)(k+2)(k+1)}{30} - \frac{(k+2)(k+1)}{50} + \frac{76(k+1)}{25}\right.\\
+                  &  \qquad\quad \left. + \frac{626}{125} - \frac{4}{250}
+                  \left( \left(\frac{1+i\sqrt{5}}{6}\right)^k(94-25\sqrt{5}i)+\left(\frac{1-i\sqrt{5}}{6}\right)^k(94+25\sqrt{5}i) \right)
+                  \right)
+    \end{align*}
+    and from $n=6$ and onwards, the expression becomes complicated and Mathematica can only give expressions including roots of polynomials.
+
     ~
 
 	If statements \ref{it:pos}-\ref{it:lim} are true, then we can define the function