Problem: (Stanford Putnam Practice) Suppose is a sequence of positive integers satisfying for . Show that for each .
Solution: Let be an arbitrary positive integer. If we can show that we will be done. We have
so . Then for some positive integer . Similarly, we know so for some positive integer . Then, however,
so we must have . Thus . QED.
Comment: At first, induction seemed the way to go, but after a while you realize that the induction step is, well, not very likely since puts very few restrictions on . So then you look to a better option, trying to find the strongest use of . It turns out that this happens when is a multiple of , which is exactly how the above proof starts.
Practice Problem: (Stanford Putnam Practice) Let be a prime number. Show that divides infinitely many of the numbers
Leave a Reply
You must be logged in to post a comment.