Use mathematical induction to prove that a function F deﬁned by specifying F (0) and a rule for obtaining F (n+1) from F (n)is well deﬁned. Im just not sure what the question is asking me to prove, or how to prove it with induction.
 A: Hint: The result is in a certain sense obvious. We know $F(0)$, the rule tells us how to find $F(1)$, then the rule tells us how to find $F(2)$, and so on.
If we want to operate very formally, there are two things to prove: (i) There is a function $F$ that satisfies the condition and (ii) There is only one such function.  I believe that (depending on the nature of your course) you are not supposed to even notice that (i) needs to be proved. So let us concentrate on (ii).
We need to prove the following result: 
Theorem: Suppose that $F(0)=G(0)$ and that for every non-negative integer $n$  we have $F(n+1)=h(F(n))$ and $G(n+1)=h(G(n))$, where $h$ is some function. Then $F(n)=G(n)$ for every non-negative integers $n$.
Now that the result has been stated formally, the induction proof should be very straightforward. All we need to show is that if $F(k)=G(k)$, then $F(k+1)=G(k+1)$. 

For part (i) we can do much the same thing in smaller steps.
First we prove by induction on $n$ that there exists exactly one function $F_n$ defined on the set $\{0,1,2,\ldots,n\}$ which satisfies the recursion rule for those inputs it is defined for. In the induction step, we can get $F_{n-1}$ from the induction hypothesis and then construct $F_n$ as
$$ F_n(x) = \begin{cases} F_{n-1}(x) & \text{when }x<n \\
\langle\text{recursion rule applied to }F_{n-1}(n-1)\rangle & \text{when }x=n \end{cases}$$
After this proof, we construct an $F$ defined on all of $\mathbb N$ by
$$ F(n) = F_n(n) \text{ where $F_n$ is the uniquely given function on $\{0,1,\ldots,n\}$ from before}$$
and then we must prove that this combined $F$ satisfies the recursion rule everywhere.
