$[20$ points total$]$ Mobile, ad$-$hoc networks grow through the arrival of new participants that join by linking into

the existing network.

Here is a simple example of such a model. The system begins with a single node v$1.$ Nodes then join one at

a time; as each node joins, it links itself to a single node already in the network, chosen uniformly at random.

That is$,$ if the system already contains nodes v$1,...,$ vj$1$ and node vj comes along, it joins the others by

randomly selecting one of the nodes v$1,...,$ vj$1$ and creating a link to that node.

As the network is built, over time we will observe that node vj will have a single outgoing link to one node

behind it in v$1,...$vj$1,$ but may have several incoming$$or even no links$$from nodes ahead of it in vj$+1....$

Given the random process described above, what is the expected number of incoming links to node vj in

the resulting network? Give an exact formula in terms of n and j$,$ and also try to express this quantity

asymptotically $($via an expression without large summations$)$ using $\backslash$Theta $()$ notation. HINTS: consider all nodes

vk that come after vj $.$ Look up the sum of the harmonic series in the Computer Science Cheat Sheet,$2$ on

Canvas under Supporting Documents, and its $\backslash$Theta approximation. You may have to split the sum.