Examples 2.3.8:
Which of the following two recursive definition is valid ?
- Let x0 = x1 = 1 and define xn = xn - 1 + xn - 2 for all n > 1.
- Select the following subset from the natural numbers:
- x0 = smallest element of N
- xn = smallest element of N - {x0 , x1 , x2 , ..., xn + 1}
- Suppose we let x0 = x1 = 1 and define xn = xn - 1 + xn - 2 for all n > 1. Then the first element is uniquely determined, and each following element to be selected depends only on the ones that have already been selected. Hence, this is a valid recursive definition. Note that to compute, say, x5 , we need to compute all previous numbers first. The numbers defined in this way are called Fibonacci numbers.
- This is not a valid recursive definition, because to find the element x2, say, we need to find the smallest element of the set N - {x0 , x1 , x2 , x3}. Since this definition involves the element x2 itself (and also x3) which we do not know at this stage, this recursive definition is not valid.