This is part of self-study; this question is taken from "Discrete Mathematics and Its Applications" (Rosen).
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.
I encountered a proof for this, but I'm not sure why it is valid.
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.
The idea of this proof is that, if there are n Ulam numbers, for example, there is always $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$.
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, and the sum has to be unique.
In fact, the idea used in this proof is similar to Euclid's proof that there are infinitely many primes.
Euclid's proof that there are infinitely many primes (taken from http://primes.utm.edu/notes/proofs/infinite/euclids.html): "Call the primes in our finite list $p_1$, $p_2$, …, $p_r$. Let P be any common multiple of these primes plus one (for example, P = $p_1p_2…p_r+1$). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of $p_1$, $p_2$, …, $p_r$, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete."
There is a great similarity between these proofs: both create a new number from the original list of n numbers. The problem is that, in Euclid's proof, there is the fact any integer greater than 1 must be a product of primes (or powers of primes). Then, the sum of all primes in the list plus 1 must be a product of primes. So, there is no need that the newly created number must be a prime, because, if it is not a prime, it can be assured that it must have in its composition prime numbers that are not in the original list. This assures that there is some non-specified prime greater than the ones on the list.
In the case of Ulam numbers, if $u_n + u_{n-1}$ is not a Ulam number, how can I assure that there is still an Ulam number that is greater than $u_n$?
Best Answer
You’ve misunderstood the proof that the set of Ulam numbers is infinite. It does not say that $u_n+u_{n-1}$ will always be an Ulam number: it says that if there are only finitely many Ulam numbers, and if $u_n$ and $u_{n-1}$ are the two largest Ulam numbers, then $u_n+u_{n-1}$ would have to be another Ulam number. This contradicts the assumption that $u_n$ and $u_{n-1}$ are the two largest Ulam numbers. But we know that given any finite set of numbers with at least two members, we can always pick out the two largest, so if the set of Ulam numbers were finite, we could certainly choose $u_n$ and $u_{n-1}$ to be the two largest Ulam numbers. Thus, the real problem is the assumption that there are only finitely many Ulam numbers, and the contradiction shows that this cannot be the case, i.e., that there must be infinitely many Ulam numbers.
To recapitulate the argument in a little more detail:
If $U$ is a finite set of positive integers, the largest possible sum of two members of $U$ is obtained by adding the two largest members of $U$, and every other pair will have a smaller sum. Thus, if $U$ were the entire set of Ulam numbers, and if $u_n$ and $u_{n-1}$ were the two largest members of $U$, then $u_n+u_{n-1}$ would be the largest possible sum of two members of $U$, and $u_n$ and $u_{n-1}$ would be the only two members of $U$ having that sum. But that would by definition make $u_n+u_{n-1}$ an Ulam number not in $U$, contradicting the supposition that $U$ contained every Ulam number. Thus, no such set $U$ can exist, and the set of Ulam numbers must be infinite.