"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)


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?

  • 2
    $\begingroup$ 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$. $\endgroup$ – Mauro ALLEGRANZA Sep 5 '18 at 19:24
  • $\begingroup$ Probably that if $x=y$ then $f_n(x)=f_n(y)$ for $n\in\mathbb{N}$. $\endgroup$ – M. Nestor Sep 5 '18 at 19:29
  • $\begingroup$ @MauroALLEGRANZA Thank you for the quick answer. I feel incredibly stupid for not think about that before posting. Thank you once again. $\endgroup$ – E.Bob Sep 5 '18 at 19:34

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.