Recurrence Relation

How do you compute up[v][j] for $j \geq 1$? Use this recurrence:

up[v][j] = up[up[v][j-1]][j-1]

In words: to jump $2^j$ steps from $v$, first jump $2^{j-1}$ steps (landing at up[v][j-1]), then jump another $2^{j-1}$ steps from there. Since $2^{j-1} + 2^{j-1} = 2^j$, you have jumped the right distance. This is the same idea as repeated squaring in fast exponentiation. Break the big jump into two equal halves.