So here is another take on the answer:
First we will use induction: assume that for some $N$, $(u_k)_{2\leq k\leq N}$ is (non-strictly) increasing.
What is the purpose of a weighing?
If we have an unequal number of balls on each side, it's potentially useless since having the side with more balls being heavier than the other side gives us no information. So we can assume that there are an equal number of balls on either side.
If so, the weighing allows us to split the balls into 3 groups, two of the same size, and determine which has the ball.
So now how do we complete our proof?
It suffices to show that if we have a strategy for weighing with $N+1$ balls, we can convert into a strategy for $N$ balls with the same number or fewer weighings.
Let's split into a couple of cases as follows:
Consider the three groups we split the $N+1$ balls into initially for its strategy, suppose they have sizes $a$, $a$ and $b$.
Case 1: $b>0$
Then we can solve $N$ balls by weighing the same groups with sizes $a$, $a$ and $b-1$ initially, since the previous strategy takes $\geq 1+\max(u_a,u_b)$ turns and this one takes $1+\max(u_a,u_{b-1})\leq 1+\max(u_a,u_b)$ turns by our induction.
Case 2: $b=0$
Then we can solve $N$ balls by weighing groups with sizes $a-1$, $a-1$, $1$ (clearly $N\geq2$), since the previous strategy takes $\geq 1+u_a$ turns and this one takes $1+u_{a-1}\leq 1+u_a$ turns by our induction.
A small nuance:
Really we have to have $u_0$ and $u_1$ defined for this - clearly the first is impossible (so can never be an outcome of a weighing) and the second is $0$.
Another problem
As @ffao points out, there is a hole in my argument:
"the case after the first weighing is not u_a nor u_b, because you have extra information: more specifically, you have at your disposal either a+b or 2a balls that are guaranteed to have the regular weight."
However I believe it can be fixed:
We claim that if you have an arbitrary fixed number of balls of normal weight (in both cases), the amount of weighings is not affected. Clearly, you should only have "extra" balls on one side of the scale (otherwise they cancel out) so these balls allow you to check three sets of potentially different cardinality, $a$, $b$ and $c$ where we "compare" $a$ and $b$.
For the $c>0$ case things are fine, since if we could compare $a$ and $b$ before we can after. Also with $c=0$, our comparison of $a-1$ and $b-1$ is also still possible as you need the same number of extra normal balls on the lighter side to keep things equal.