Someone asked me how you prove that defining a function recursively actually defines a function, and then I tried to rigorously prove it. Is it right?
Let $\mathbb{N}=\{0,1,2,\dots\}$. For any natural number $x$ and any function $g:\mathbb{N} \longrightarrow \mathbb{N}$, there is precisely one function $f:\mathbb{N} \longrightarrow \mathbb{N}$ having the following properties:
(1) $f(0)=x$ and (2) $f(n+1)=g(f(n))$ for all $n \in \mathbb{N}$.
Proof: Let $N(t)$ denote the initial segment $\{0,1,2,\dots,t\}$ of the natural numbers. We define functions $f^t: N(t) \longrightarrow \mathbb{N}$, for every $t \in \mathbb{N}$, such that: (1) $f^t(0)=x$ and (2) $f^t(n+1)=g(f^t(n))$ for all $n \in N(t-1)$.
For $n=0$ we simply say $f^0={(0,x)}$. This has property (1), and vacuously property (2). Now we define the function $f^{t+1}$, given that $f^t$ exists, by saying $f^{t+1}=f^t \cup {t+1, g(t)}$. This clearly inherits properties (1) and (2) from $f^t$, so we have that $f^t$ exists for all $t \in \mathbb{N}$, by induction.
Now we let $f$ be the union over $\mathbb{N}$ of all the "initial" functions $f(t)$. This defines a function because the $f^t$ are all functions, each nested inside the next. It inherits properties (1) and (2) from the $f^t$. Q.E.D.
What you have so far proves that a function satisfying (1) and (2) exists. To prove that it is unique you have to also prove that if $h$ is any function satisfying (1) and (2) then $f(n)=h(n)$ for all $n \in \mathbb N$. This is most easily proved by induction on $n$.