Recurrence Example

Say you want up[v][2], the $4$th ancestor of $v$. First, jump $2$ steps: up[v][1] is the grandparent. Then jump another $2$ steps from there: up[up[v][1]][1]. You have jumped $2 + 2 = 4$ steps total. So:

up[v][2] = up[up[v][1]][1]

This pattern holds for all $j$. Every column depends only on the previous column, so you compute columns in order from $0$ to $\log n$. Each entry is filled in $O(1)$ time.