I am asked to solve the following recurrence problem: $$A(0)=0,\quad A(n)=1+\min_{1\leq k\leq n}\left\{\max\left(\left\lfloor\frac{k-1}{2}\right\rfloor, A(n-k)\right)\right\}\,. $$
I have observed that for $n=0,1,2,3,\ldots$, the values of $A(n)$ are
$$0,1,1,2,2,2,2,3,3,3,3,3,3,4,4,\ldots\,,$$
namely, the sequence $A(n)$ includes two $1$’s, four $2$’s, six $3$’s, eight $4$’s, ten $5$’s, etc. Therefore, my guess is that $A(n)$ is the smallest $m\in\mathbb{N}$ such that $m(m+1)\geq n$, or equivalently,
$$A(n)=\left\lceil\frac{-1+\sqrt{4n+1}}{2}\right\rceil\,,$$
which seems to produce the correct sequence. However, I don't know how to prove this. The hint I received is to find a simple expression for any of the values $k$ that minimize the term
$$\max\left(\left\lfloor\frac{k-1}{2}\right\rfloor, A(n-k)\right)$$
for some $n$, which I cannot figure out. Any tips or solutions will be appreciated.