Use principle of mathematical induction to show a function defined recursively is uniquely determined.

Question

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions.

"Use the Principal Of Mathematical Induction to show that the value at each positive integer of a function defined recursively is uniquely determined."

A Recursive Function is defined previously as:

Definition: We say the function f is defined recursively if the value of f at 1 is specified and if a rule is provided for determining f(n+1) from f(n).

The question implies a general proof. But as far as I can gauge the only way I can be sure a recursive function is indeed uniquely determined is if I know what the actual function involved is?

e.g. a recursive function could be defined such that the RHS was fully a square root term implying 2 solutions?

Answer 1

Hint:

Let $f:N\to R$,

$f':N\to R$,

$g:R\to R$,

$f(1)=f'(1)=x_1\in R$,

$f(x+1)=g(f(x))$,

$f'(x+1)=g(f'(x))$.

Note that:

$f(1)=x_1$,

$f(2)=g(x_1)$,

$ f(3)=g(g(x_1))$,

$f(4)=g(g(g(x_1)))$, ...

Similarly for $f'$.

Prove by induction that for all $x\in N$, we have $f(x)=f'(x)$.

Base case: Prove $f(1)=f'(1)$.

Inductive Step: Suppose $f(k)=f'(k)$. Prove $f(k+1)=f'(k+1)$.