# Principle of mathematical induction in recursive functions

"Use the principles of mathematical induction to show that the value at each positive integer of a function defined recursively is uniquely determined"

I have a problem understanding what exactly it wants me to show. Does it want me to show that

A: for a positive integer $n_1$, the value of the recursive function $f(n_1)$ is unique, meaning that there are no other positive integers $n$ such that $f(n)=f(n_1)$ (show that $f$ is injective)

or

B: functions $f$ and $g$ must be the same function if for every positive integer $n$: $f(n)=g(n)$, therefore proving uniqueness.

I have solved it for B but not sure about my solution in A. Do I continue with A or have I solved it assuming my solution is correct in B?

• Of course, A is wrong. The function $f(n)=0$ is a recursive function but $f(n_1)=f(n_2)$ for every $n_1,n_2$. – Mauro ALLEGRANZA Sep 5 '18 at 19:24
• Probably that if $x=y$ then $f_n(x)=f_n(y)$ for $n\in\mathbb{N}$. – M. Nestor Sep 5 '18 at 19:29
• @MauroALLEGRANZA Thank you for the quick answer. I feel incredibly stupid for not think about that before posting. Thank you once again. – E.Bob Sep 5 '18 at 19:34

## 1 Answer

The aim of the task is essentially to show that a recursive definition of a function actually defines a function. To make things more formal, if $X$ is a set and $x_1\in X$ an element of it and we have a function $F\colon \Bbb N\times X\to X$, then we can ask ourselves how many functions $f\colon \Bbb N\to X$ exist with the properties $$\tag1 f(1)=x_1,\qquad\forall n\in\Bbb N\colon f(n+1)=F(n,f(n)).$$ Perhaps none, perhaps many? The important answer is that there exists exactly one such function. Your task in this problem is to show uniqueness, that is:

Claim. If $f_1,f_2$ are functions $\Bbb N\to X$ for which $(1)$ holds, then $f_1=f_2$ (i.e., $f_1(n)=f_2(n)$ for all $n\in\Bbb N$).

It may be of little surprise that this requires induction on $n$.

• Got it solved, thank you! – E.Bob Sep 5 '18 at 19:35