[Yao] (“Fringe analysis of 2–3 trees [25]”) Solve the recurrence
$$A_N = A_{N-1}-{2A_{N-1}\over N} + 2\Bigl(1-{2A_{N-1}\over N}\Bigr)$$This recurrence describes the following random process: A set of N elements is collected into “2-nodes” and “3-nodes.” At each step each 2-node is likely to turn into a 3-node with probability $2/N$ and each 3-node is likely to turn into two 2-nodes with probability $3/N$. What is the average number of 2-nodes after $N$ steps?
Solving recurrence by empirical experiment:
$$\eqalign{ A_N &= A_{N-1}-{2A_{N-1}\over N} + 2\Bigl(1-{2A_{N-1}\over N}\Bigr)\\ A_0 &= 0\\ A_1 &= A_0-\frac{2A_0}{1} + 2 - 2\frac{2A_0}{1} = 0 - 0 + 2 - 0 = 2\\ A_2 &= A_1-\frac{2A_1}{2} + 2 - 2\frac{2A_1}{2} = 2 - 2 + 2 - 4 = -2\\ A_3 &= A_2-\frac{2A_2}{3} + 2 - 2\frac{2A_2}{3} = -2 + 4/3 + 2 + 8/3 = 4\\ A_4 &= A_3-\frac{2A_3}{4} + 2 - 2\frac{2A_3}{4} = 4 - 8/4 + 2 - 16/4 = 0\\ A_5 &= A_4-\frac{2A_4}{5} + 2 - 2\frac{2A_4}{5} = 0 - 0/5 + 2 - 0/5 = 2\\ A_6 &= A_5-\frac{2A_5}{6} + 2 - 2\frac{2A_5}{6} = 2 - 4/6 + 2 - 8/6 = 2\\ A_7 &= A_6-\frac{2A_6}{7} + 2 - 2\frac{2A_6}{7} = 2 - 4/7 + 2 - 8/7 = 16/7 = 2.285714285714286\\ A_8 &= A_7-\frac{2A_7}{8} + 2 - 2\frac{2A_7}{8} = 16/7 - (32/7/8) + 2 - (64/7/8) = 18/7 = 2*9/7 = 2.571428571428571\\ A_9 &= A_7-\frac{2A_8}{9} + 2 - 2\frac{2A_8}{9} = 18/7 - (18/7/9) + 2 - (18/7/9) = 20/7 = 2*10/7 = 2.857142857142857\\ A_{10} &= A_9-\frac{2A_9}{10} + 2 - 2\frac{2A_9}{10} = 20/7 - (20/7/10) + 2 - (20/7/10) = 22/7 = 2*11/7 = 3.142857142857143 = \pi\\ ...\\ A_{21} &= A_{20}-\frac{2A_{20}}{21} + 2 - 2\frac{2A_{20}}{21} = 2*22/7 = 2\pi\\ ...\\ A_{43} &= A_{42}-\frac{2A_{42}}{43} + 2 - 2\frac{2A_{42}}{43} = 2*2*22/7 = 4\pi\\ ...\\ }$$So:
$$ A_N \begin{cases} \begin{pmatrix} 0 & 2 & -2 & 4 & 0 & 2 & 2\end{pmatrix},& \text{if } N \leq 6\\ 2(N+1)/7 & \text{otherwise} \end{cases} $$Proof:
Apply Theorem 2.1 $$\eqalign{ A_N &= A_{N-1}-{2A_{N-1}\over N} + 2\Bigl(1-{2A_{N-1}\over N}\Bigr)\\ A_N &= A_{N-1}-{2A_{N-1}\over N} + 2 -2{2A_{N-1}\over N}\\ NA_N &= NA_{N-1}-2A_{N-1} + 2N -4A_{N-1}\\ A_N &= \frac{(N-6)A_{N-1}}{N} + 2\\ A_N &= (1-6/N)A_{N-1}+2\\ }$$
Extend the equation into general form:
$$\eqalign{ X_N &= \prod_6^N(1-6/i) \quad \text{and} \ B_N = A_N/X_N \ \text{for} \ X_6=1\\ B_N &= B_{N-1}+2/X_N \quad \text{for} \ i>1\\ B_N &= B_6+2\sum_{i=7}^N(1/X_i)\\ -----\\ \sum_{i=7}^N(1/X_i) &= \sum_{i=7}^N\frac{i(i-1)...(i-5)}{6!}\\ &= \sum_{i=7}^N\frac{(i+1)i(i-1)...(i-5)-i(i-1)...(i-5)(i-6)}{7!}\\ &= \frac{(N+1)N(N-1)...(N-5)}{7!}-1\\ -----\\ B_N &= \frac{(N+1)N(N-1)...(N-5)}{7!} \quad \text{for} \ i>6\\ A_N &= B_NX_N = 2(N+1)/7 \quad \text{for} \ i>6\\ }$$Find the the average number of 2-nodes: $$\eqalign{ A_N &= A_{N-1}-{2A_{N-1}\over N} + 2\Bigl(1-{2A_{N-1}\over N}\Bigr)\\ \overline{A_{2-nodes}} &= A_{N-1}-(1 - {2A_{N-1}\over N}) + 2\Bigl(1-{2A_{N-1}\over N}\Bigr) \quad \text{reduce to probabilty of only 2-nodes}\\ }$$
thus, $$\overline{A_{2-nodes}} = 2(N+1)/7 - 1 \quad for \ i>6$$
Plot the periodic part of the solution to the recurrence: $$a_N = 3a_{\lfloor N/3\rfloor} + N \quad{\rm for}\ N>3{\rm \ with\ } a_1=a_2=a_3=1$$ For $1 \leq N \leq 972$
Solution:
For $k\geq 0$, $a_{\lfloor N/3^k\rfloor} = 3a_{\lfloor N/3^{k+1}\rfloor} + \lfloor N/3^k\rfloor$ holds true as long as $\lfloor N/3^k\rfloor \geq 4$ (which is equivalent to $k\leq log_3(N/4)$)
Noting $K:=\lfloor log_3(N/4)\rfloor$, $b_k:=3^ka_{\lfloor N/3^k\rfloor}$, we have $b_k=b_{k+1}+\lfloor N/3^k\rfloor 3^k$ for $0\leq k\leq K$
Our target is $b_0=a_N$, and we know $b_{K+1}=3^{K+1}$, $b_0$ could be obtained quite directly by:
$$a_N = b_0 = 3^{K+1} +\sum_{k=0}^K\lfloor N/3^k\rfloor 3^k \ \text{with} \ K=\lfloor log_3(N/4)\rfloor$$We could write thus $a_N\sim Nlog_3N$
Here is the plot of $a_N$ and $Nlog_3N$
In [ ]: