- #1

- 205

- 3

I was self-studying Discrete Mathematics from a book and found the following problem:

## Homework Statement

We define the Ulam numbers by setting u

_{1}= 1 and u

_{2}= 2. Furthermore, after determining whether the integers less than n are Ulam numbers, we set n equal to the next Ulam number if it can be written uniquely as the sum of two different Ulam numbers. Note that u

_{3}= 3, u

_{4}= 4, u

_{5}= 6, and u

_{6}= 8. Prove that there are infinitely many Ulam numbers.

**2. The attempt at a solution**

I imagine that I have to show that, if there are n Ulam numbers, for example, there is always an u

_{n+1}. To show this, I have to show somehow that there will always be two numbers among these n numbers whose sum is unique and greater than u

_{n}. If it were the case that u

_{n}is the greatest Ulam number, it would mean that no sum between two of the numbers is unique and greater than u

_{n}. I had no clue on how to continue, so I searched on the Internet and found the following proof method:

Assume that there are only finitely many Ulam numbers. Let the two largest Ulam numbers be u

_{n-1}and u

_{n}. Then the integer u

_{n-1}+ u

_{n}is an Ulam number larger than u

_{n}. It is the unique sum of two Ulam numbers, since it is the largest sum between two of the n Ulam numbers.

While trying to understand this proof, I found that there seems to be something wrong, because it is not always true that, for n Ulam numbers, u

_{n-1}+ u

_{n}will be an Ulam number. For example, consider the n Ulam numbers with n = 3: 1, 2, 3. The sum 3 + 2 = 5 is not an Ulam number, because 4 is an Ulam number and 4 + 1 = 5.

Thank you in advance.