- #1
a7d07c8114
- 22
- 0
Homework Statement
Use the principle of mathematical induction to show that the value at each positive integer of a function defined recursively is uniquely determined.
I understand the problem and its related concepts. However, I feel that my attempt at a proof doesn't use the principle of mathematical induction properly. I would appreciate any insight into the solution.
This problem is taken from Rosen's Elementary Number Theory and Its Applications, page 16.
Homework Equations
The Principle of Mathematical Induction. A set of positive integers that contains the integer 1 and the integer n+1 whenever it contains n must be
the set of all positive integers.
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 Attempt at a Solution
Let there exist a recursively defined function f, whose domain is all n such that n is a positive integer. For n=1, the value of f(1) is arbitrarily specified, and therefore the value of f has a unique determination at 1.
Assume there is a value of n such that f(n) is uniquely determined. Assume f(n+1) is not uniquely determined. Then the determination of f(n+1) must be the same as the determination of f(m), where m is a positive integer less than n+1. Assume n+1=2. Then m=1, since 1 is the the only number in the domain of f less than 2. Then f(2) must have the same determination as f(1). But f(1) is defined to be uniquely determined, leading to a contradiction. Therefore, f(2) must also be uniquely determined.
Assume n+1=3. Then m must be either 1 or 2...
This process can be continued infinitely. Therefore f(n+1) must be uniquely determined. By the Principle of Mathematical Induction, it can therefore be concluded that f(n) is uniquely determined at all positive integer values of n.