Explaining why a function is well-defined How can I explain that a function is well-defined, if it's defined recursively by specifying $f(1)$, and a rule for finding $f(n)$ from $f(n-1)$?
My reasoning: If the function for $f(n)$ can be derived from $f(n-1)$, then the function must give a unique value for each input, which is part of what being well-defined is. And since I have $f(1)$, then I can prove any other function starting with that one, so it IS well-defined.
 A: "Well-defined" is a somewhat fuzzy term. But here, it seems that you want to ensure that a function that is defined at $1$ and then you have a recursive definition explaining how to obtain $f(n)$ from $f(n-1)$ does in fact lead to a function whose domain is all the natural numbers.
The answer is that this follows from the Recursion Theorem.
Recursion Theorem. Let $X$ be a set, let $a\in X$, and let $g\colon X\to X$ be a function. Then there exists a unique function $u\colon\mathbb{N}\to X$ such that $u(1)=a$ and $u(n+1) = g(u(n))$ for all $n$.
So here, $X$ is the codomain of $f$; $a$ is the value of $f(1)$; and $g$ is the function that corresponds to your rule for finding $f(n)$ from $f(n-1)$. The Recursion Theorem ensures the existence of a function whose domain is all of $\mathbb{N}$ that has the property you want.
The proof of the recursion theorem is by induction. What follows is the argument in Halmos's Naive Set Theory, pages 48-49.
Remember that we can consider a function $\mathbb{N}\to X$ as a set $u$ of ordered pairs $(n,x)$, where for each $n\in \mathbb{N}$ there is an $x$ in with $(n,x)\in u$; and if $(n,x)$ and $(n,y)$ are both in $u$, then $x=y$.
Consider the collection of all relations $A$ between $\mathbb{N}$ and $X$ that contain $(1,a)$, and such that if $(n,x)\in A$, then $(n+1,g(x))\in A$. The collection is nonempty (the total relation satisfies the properties), so we may consider the intersection of all sets in the collection. Call this intersection $u$; we need to show that $u$ is a function defined on all natural numbers.
Let $S$ be the set of all natural numbers $n$ for which there is exactly one element $x$ of $X$ such that $(n,x)\in u$. We show $S=\mathbb{N}$ by induction.
If $1\notin S$, then there exists $b\neq a$ such that $(1,b)\in u$. But then $u-\{(1,b)\}$ still contains $(1,a)$, and if it contains $(n,x)$ then it contains $(n+1,g(x))$; so $u-\{(1,b)\}$ is one of the relations in our collection, which is impossible (since it is properly contained in the intersection of all such relations). So $1\in S$.
Now suppose that $n\in S$; Then there is a unique $x\in X$ such that $(n,x)\in u$. By the properties of $u$, $(n+1,g(x))\in u$. If $n+1\notin S$, then there exists $y\in X$, $y\neq g(x)$, such that $(n+1,y)\in u$. Then consider $u-\{(n+1,y)\}$ and derive a similar contradiction. So $n+1\in S$.
By induction $S=\mathbb{N}$, so $u$ is a function from $\mathbb{N}$ to $X$, as desired.
A: Here’s a much stronger version of the recursion theorem then the one presented in Arturo Magidin’s answer.

Let $X$ be a set,  let $X^{<\omega}$ denote the set of all finite sequences of elements of $X$ , let $[n]$ denote $\{0,1,2,…,n-1\}$ for $n\in \omega$. Suppose $g:X^{<\omega}\to X$ then there exists a unique function $f:\omega \to X$ such that $f(n)=g(f\restriction [n])$ for all $n \in 
\omega $.

One  can prove existence and uniqueness quite easily , by building approximations to $f$, and then “pasting them together”.This version is much stronger, because it “allows access” to $(f(0),f(1),f(2),…,f(n-1))$. This also  lets us handle things like the Fibonacci sequence and much more.
