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