Problem

Source: Mexico National Olympiad Mock Exam 2018 Problem 6

Tags: combinatorics, elements of set



Let A be a finite set of positive integers, and for each positive integer n we define Sn={x1+x2++xn|xiA for i=1,2,,n} That is, Sn is the set of all positive integers which can be expressed as sum of exactly n elements of A, not necessarily different. Prove that there exist positive integers N and k such that |Sn+1|=|Sn|+k for all nN. Proposed by Ariel García