You’ve misunderstood the proof that the set of Ulam numbers is infinite. It does not say that $u_n+u_{n-1}$ will always be an Ulam number: it says that if there are only finitely many Ulam numbers, and if $u_n$ and $u_{n-1}$ are the two largest Ulam numbers, then $u_n+u_{n-1}$ would have to be another Ulam number. This contradicts the assumption that $u_n$ and $u_{n-1}$ are the two largest Ulam numbers. But we know that given any finite set of numbers with at least two members, we can always pick out the two largest, so if the set of Ulam numbers were finite, we could certainly choose $u_n$ and $u_{n-1}$ to be the two largest Ulam numbers. Thus, the real problem is the assumption that there are only finitely many Ulam numbers, and the contradiction shows that this cannot be the case, i.e., that there must be infinitely many Ulam numbers.
To recapitulate the argument in a little more detail:
If $U$ is a finite set of positive integers, the largest possible sum of two members of $U$ is obtained by adding the two largest members of $U$, and every other pair will have a smaller sum. Thus, if $U$ were the entire set of Ulam numbers, and if $u_n$ and $u_{n-1}$ were the two largest members of $U$, then $u_n+u_{n-1}$ would be the largest possible sum of two members of $U$, and $u_n$ and $u_{n-1}$ would be the only two members of $U$ having that sum. But that would by definition make $u_n+u_{n-1}$ an Ulam number not in $U$, contradicting the supposition that $U$ contained every Ulam number. Thus, no such set $U$ can exist, and the set of Ulam numbers must be infinite.
Suppose $k$ is a positive integer and $p$ is a prime such that $k^3+pk^2$ is a perfect cube.
Consider two cases . . .
Case $(1)$:$\;p{\,\mid\,}k$.
Write $k=p^nj$ with $n\ge 1$ and $\gcd(j,p)=1$.
Then we have
$$
k^3+pk^2
=
p^{2n+1}j^2(p^{n-1}j+1)
$$
hence, noting that the factor $j^2$ is relatively prime to each of the factors
$$
p^{2n+1},\;\;\;p^{n-1}j+1
$$
it follows that $j^2$ must be a perfect cube.
Since $j^2$ is a perfect cube, so is $j$.
Claim $n\equiv 1\;(\text{mod}\;3)$.
We can assume $n > 1$, since for $n=1$, the claim is automatic.
Then in the factorization
$$
k^3+pk^2
=
p^{2n+1}j^2(p^{n-1}j+1)
$$
the factor $p^{2n+1}$ is relatively prime to each of the factors
$$
j^2,\;\;\;p^{n-1}j+1
$$
hence $p^{2n+1}$ must be a perfect cube, so $n\equiv 1\;(\text{mod}\;3)$, as claimed.
It follows that $p^{n-1}j$ is a perfect cube, equal to $x^3$ say, for some $x\ge 1$.
But then
$$
p^{n-1}j+1=x^3+1
$$
is strictly between $x^3$ and $(x+1)^3$, so can't be a perfect cube.
Thus case $(1)$ is impossible.
Case $(2)$:$\;p{\,\not\mid\,}k$.
Then we have
$$
k^3+pk^2
=
k^2(k+p)
$$
hence, noting that the factors
$$
k^2,\;\;\;k+p
$$
are relatively prime, it follows that they must both be perfect cubes.
Since $k^2$ is a perfect cube, so is $k$.
Thus $k=x^3$ and $k+p=y^3$ for some $x,y\ge 1$, so we get
$$
p=y^3-x^3=(y-x)(y^2+xy+x^2)
$$
hence since $p$ is prime, we must have $y-x=1$.
Then we get
$$
p=y^3-x^3=(x+1)^3-x^3=3x^2+3x+1
$$
hence $p\equiv 1\;(\text{mod}\;3)$, as was to be shown.
Best Answer
Let's adopt a new notation $T(n)=\frac{n(n+1)}{2}$ and $H(n)=2n^2-n$
The aim is to prove $T(n)=H(m)$ for some $n,m$.
This gives $\frac{n(n+1)}{2}=2m^2-m=m(2m-1)\iff n(n+1)=(2m-1)2m$
Under this form it is obvious that $n=2m-1$ works and $T(2m-1)=H(m)$ or equivalently $H(\frac{n+1}{2})=T(n)$ (for $n$ odd).
Don't be surprised by your formula though, because in fact
$T(-n)=\frac{-n(-n+1)}{2}=\frac{n(n-1)}{2}=T(n-1)$
And you get $H(n)=T(-2n)=T(2n-1)=H(n)$ and the cycle is complete.