Let be a positive integer greater than . Prove: for every non-negative integer there exist positive integers , such that
Solutions — 2
Solution 1
Let . If and , then . If and , then . In both cases, is an arbitrary non-negative integer. Hence, the equation has solutions for all positive integers .
Next, we consider the case . Let , and . Then . For every non-negative integer there exists a solution to the equation . so we have shown that the equation has solutions for all non-negative integers .
For we proceed by induction. Assume that the equation has positive integer solutions for all non-negative integers and for all positive integers such that . We wish to show that in this case the equation also has positive integer solutions for all non-negative integers .
Since and , the induction hypothesis implies that for all non-negative integers there exist positive integers , such that
In particular, this is true for . so there exist positive integers , such that
Solution 2
Since and , such numbers and exist for , and for , . Using induction on we show that the solutions exist for any . Let . Assume that there exist positive integers , such that . Then
so is the sum of the squares of two positive integers. We have considered the cases and separately, so by induction the claim for follows for all non-negative integers .
Since and , we can use a similar argument for and show that the equation also has positive integer solutions for all non-negative integers .
Let . We will use induction on . Assume that for all non-negative integers there exist positive integers , such that
and, since , positive integers , such that
If is even, then . So is a sum of squares of positive integers.
Let be odd. Since , we can find two positive integers , such that . Then
Since was an arbitrary non-negative integer, this concludes the induction.