I've got some problems with the following:
Let $C(x)$ be the unary predicate "is a square" (so, for example, $C(4)$, $C(9)$ are true). I want to prove that the function $q(x)=x^2$ is definable in $(\mathbb{N}, +, C)$, i.e. there is a formula $\phi(x,y)$ such that $\phi(a,b) \leftrightarrow b=a^2$.
I was thinking about something like $C(x) \land z=f(x) $, where $f(x)$ is some expression containing only the + and without any form of recursion.
I can't think of anything, because I can find way to write $x^2$ only using multiplication or using $(x-1)^2$, which I cannot write using only $C$ and $+$. Have you got some suggestions?
Addition is more expressive than you might think:
The ordering $<$ on $\mathbb{N}$ is definable from $+$: $a<b\iff\exists c(a+c=b)$.
With $<$ in hand, we can talk about "next" - given a number $x$ and a formula $\varphi$, the next $y$ after $x$ satisfying $\varphi$ is the unique $y$ such that $$\varphi(y)\wedge\forall z(x<z<y\implies \neg\varphi(z)).$$
Now, can you see a way to tell whether a square $b$ happens to be the square of a given number $a$, based on comparing $a$ with the distance between $b$ and the next square after $b$?