# Understanding of recurrence relation for number of 2-nodes in 2-3 tree

$$A_N = A_{N-1} - \frac{2A_{N-1}}{N} + 2\left(1- \frac{2A_{N-1}}{N}\right),\quad \text{for}\ N > 0, A_0 = 0.$$

Probability for 2-node to become 3-node is $\frac{2}{N}$ and for 3-node to become 2-node is $\frac{3}{N}$. 2-node contains 1 element, 3-node contains 2 elements.

I think that $A_{N}$ is the number of 2-nodes on $N$th step. So, $\frac{2A_{N-1}}{N}$ is the expected number of 2-nodes which turn to 3-nodes.

From where $\left(1- \frac{2A_{N-1}}{N}\right)$ came?

EDIT: To give a context i provide picture of the exercise from An Introduction to the Analysis of Algorithms:

• I don't think you've given us enough context. Where did you encounter that formula? What was the surrounding context? What is $A_N$ defined to represent? – D.W. May 9 '18 at 5:58
• @D.W. Hi, i updated the question. – Yola May 9 '18 at 6:31