I also used to have a lot of trouble understanding this. Let me see if the following helps.
I assume we're working in some flavor of set theory and that I have already defined ordered pairs, nonnegative integers, and the notations $+$ and $\times$. I'll write $\mathbb{N}$ for the set of all nonnegative integers. Suppose I now need to define the function $n \mapsto 2^n$ from $\mathbb{N}$ to itself, and I am going to do it recursively.
Here is what I should prove:
Theorem: There is a unique subset $F$ of $\mathbb{N} \times \mathbb{N}$ such that
- For every $x \in \mathbb{N}$, there is precisely one $y \in \mathbb{N}$ such that $(x,y) \in F$.
- $(0,1) \in F$.
- If $(x,y) \in F$ then $(x+1, 2 \times y) \in F$
Then, whenever you want to write $y=2^{10}$, you instead write "Let $F$ be the unique subset of $\mathbb{N} \times \mathbb{N}$ such that ... and let $y$ be the unique element of $\mathbb{N}$ such that $(10, y) \in F$."
Of course, I haven't used fully formal language here. Statement 1, unpacks to "For all $x$ in $\mathbb{N}$, there exists $y \in \mathbb{N}$ such that $(x, y) \in F$ and, for all $x$, $y_1$ and $y_2$ in $\mathbb{N}$, if $(x,y_1) \in F$ and $(x,y_2) \in F$, then $y_1 = y_2$." A similar unpacking must be done with the statement that $F$ is unique.
This is a good point to pause and make sure you understand what I've written so far.
So, how do we prove this? I will sketch two proofs because I don't know whether you are comfortable with writing inductive proofs formally. So the first proof treats induction informally and assumes you can fill in the gaps, and the second proof fills in those gaps for you.
Proof sketch (informal induction): For $n \in \mathbb{N}$, let $\mathbb{N}_{\leq n}$ be the set of nonnegative integers less than or equal to $n$. We first show
Claim For all $n\in \mathbb{N}$, there exists a unique subset $G$ of $\mathbb{N}_{\leq n} \times \mathbb{N}$ such that
- For every $x \in \mathbb{N_{\leq n}}$, there is precisely one $y \in \mathbb{N}$ such that $(x,y) \in G$.
- $(0,1) \in G$.
- If $(x,y) \in G$ and $x then $(x+1, 2 \times y) \in G$
Our proof is by induction on $n$. If $n=0$, take $G= \{ (0,1) \}$. I leave it to you to check that this works and is unique.
For $n>0$, let G' be the subset of $\mathbb{N}_{\leq n-1} \times \mathbb{N}$ we ave inductively constructed. Let $y$ be the unique integer such that (n-1, y) \in G'. Set G = G' \cup \{ (n, 2 \times y ) \}. Again, you must check that this works and is unique.
Define $F$ to be the set of ordered pairs $(x,y)$ in $\mathbb{N} \times \mathbb{N}$ such that for some $(n, G)$ as above, the ordered pair $(x,y)$ is in $G$. The rest of the proof is left to you. $\square$
Proof sketch (formal induction): I will assume that, when you constructed $\mathbb{N}$, you proved the Well Ordering Principle:
Any nonempty subset of $\mathbb{N}$ has a least element.
Let $S$ be the set of $n$ such that there does not exist a set $G$ as in the Claim. If $S=\emptyset$, then the claim holds and we finish the proof as above.
When $n=0$, the set $\{ (0,1) \}$ satisfies the Claim (details omitted), so $0 \not \in S$. Assume for the sake of contradiction that $S$ is nonempty. Then, by the Well Ordering Principle, $S$ has a least element $n$. By the first sentence of this paragraph, $n >0$.
Since $n-1 \not \in S$, there is a set G' which satisfies the claim with respect to $n-1$. Let $y$ be the unique integer such that (n-1, y) \in G'. Set G = G' \cup \{ (n, 2 \times y ) \}. Then $G$ satisfies the claim with respect to $n$ (details omitted). So $n$ is not in $S$ after all, a contradiction. $\square$
Remark for experts I deliberately phrased the above proof to avoid the Axiom of Replacement. The full strength of the Recursion Theorem requires Replacement, but I thought it was best pedagogically to dodge this issue while I could.