Problem #PRU-73697

Problems Methods Pigeonhole principle Pigeonhole principle (other) Algebra Sequences

Problem

A sequence of natural numbers $a_{1} < a_{2} < a_{3} < \dots < a_{n} < \dots$ is such that each natural number is either a term in the sequence, can be expressed as the sum of two terms in the sequence, or perhaps the same term twice. Prove that $a_{n} \leq n^{2}$ for any $n = 1, 2, 3, \dots$

To see the solution register and get verified.