Determine all such that for some . (Italy 2005)
Solution
First notice that for even the sequence is of the form , i.e. all the terms of the sequence are odd and the sequence is monotonically increasing. Therefore for .
Let be an arbitrary odd number. We can easily show by induction that if is odd, and if is even. Thus the sequence is limited, so it is periodic.
Let be the smallest index such that for some . Assume .
If , that means that (and then also ) is derived from the previous term by dividing by 2, i.e. , , so it follows that , and this is in contradiction with minimality of .
If , from we conclude that and are derived from previous terms of the sequence by adding , so again it follows that , and again we have a contradiction with the minimality of .
Hence, and for some for every odd .