Problem:
Let be a positive integer and let be the sequence defined recursively as follows:
(For example, if we have: )
For which values of does there exist such that ?
Problem:
Let be a positive integer and let be the sequence defined recursively as follows:
(For example, if we have: )
For which values of does there exist such that ?
Solution:
The values sought are all and only the odd positive integers. Indeed, if is even, then is odd, hence is odd, and so on, so all the numbers are odd and greater than 1.
If instead is odd, we observe that all the terms of the sequence are either positive integers less than or equal to or even positive integers greater than and less than or equal to . A simple proof of this fact can be obtained using the principle of induction. As the base case, we have , which is a positive integer less than or equal to . Assuming the claim is true for , let us prove it for : if is odd and less than or equal to , then is even, greater than and less than or equal to ; if instead is even and , then .
It follows that the sequence of numbers can take only finitely many values. Since the sequence is infinite, there will exist two indices such that . Suppose we choose two indices such that and where is as small as possible. If , then and the claim is proved. Let us show by contradiction that we cannot have , distinguishing two cases:
- ; then it cannot be that or , because in that case or would not be positive, contradicting what was stated previously. Therefore , and thus we have an equality between two terms of the sequence in which the first term has an index smaller than , a contradiction;
- even, ; then it cannot be that or , because otherwise or , contradicting what was stated previously. Therefore , and again we obtain the contradiction of an equality between two terms of the sequence in which the first term has an index smaller than .