$$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:

enter image description here

  • $\begingroup$ 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? $\endgroup$ – D.W. May 9 '18 at 5:58
  • $\begingroup$ @D.W. Hi, i updated the question. $\endgroup$ – Yola May 9 '18 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.