Math Help -> Puzzles -> Increasing function B -> Answer 

A sequence x[n] of integers satisfies x[1] = 1 and x[n] < x[n + 1] < 2n + 1 for all positive integers n.  Prove that for every integer k, one can find "a" and "b" such that k = x[b] - x[a].

Consider the set, A, with k+1 elements

A = {x[1]-1, x[2]-1, ..., x[k+1]-1}.

Since the smallest element of A is 0, and the largest element of A is less than 2k, it follows that each of the numbers in A can be expressed as qk+r, where q is either 0 or 1, and r is the residue, mod k.  There are k different residues, so two of the elements in A -- call the smaller x[a]-1 and and call the larger x[b]-1 -- have the same residue, r.  This means that x[a]-1 = 0k+r, and x[b]-1 = 1k+r. Thus x[b]-x[a]=k.