## 2.3. The Principle of Induction

### Examples 2.3.8:

Which of the following two recursive definition is valid ?

- Let
*x*and define_{0}= x_{1}= 1*x*for all_{n}= x_{n - 1}+ x_{n - 2}*n > 1*. - Select the following subset from the natural numbers:
*x*= smallest element of_{0}**N***x*= smallest element of_{n}**N**- {x_{0}, x_{1}, x_{2}, ..., x_{n + 1}}

- Suppose we let
*x*and define_{0}= x_{1}= 1*x*for all_{n}= x_{n - 1}+ x_{n - 2}*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,*x*, we need to compute all previous numbers first. The numbers defined in this way are called_{5}**Fibonacci numbers**. - This is not a valid recursive definition, because to find the
element
*x*, say, we need to find the smallest element of the set_{2}. Since this definition involves the element**N**- {x_{0}, x_{1}, x_{2}, x_{3}}*x*itself (and also_{2}*x*) which we do not know at this stage, this recursive definition is not valid._{3}