Examples 2.3.8:

Which of the following two recursive definition is valid ?
  1. Let x0 = x1 = 1 and define xn = xn - 1 + xn - 2 for all n > 1.
  2. Select the following subset from the natural numbers:
    • x0 = smallest element of N
    • xn = smallest element of N - {x0 , x1 , x2 , ..., xn + 1}
Back Back
  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.
  2. 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.

Interactive Real Analysis, ver. 1.9.5
(c) 1994-2007, Bert G. Wachsmuth
Page last modified: Mar 26, 2007