# Matthew Russell # Experimental Math # Homework 18 Special # Due: April 1, 2012 # I give permission to post this ##################################################################################### # If S is a set of non-negative integers, then # mex(S) # is defined to be the smallest non-negative integers that is NOT in S. For example, # mex({0,1,2,5}) # is 3, and # mex({2,3,5}) # is 0. # Define an integer sequence by the simple recurrence # a[i]:=mex({0,1) union {seq(seq(j*a[r],j>=1),r=1..i)}): ##################################################################################### # Prove the following simple properties about this sequence # 1. There are infinitely many i such that a[i+1] - a[i]=2. # # Solution. This "statement" contains the word "infinitely", and thus is a priori meaningless. ##################################################################################### # 2. For every positive integer n > 1, there exist integers i and j such that a[i]+a[j]=2*n. # # Proof. # # Claim 1. 2 is the only even number that equals a[i] for some i. # Proof. a[1]=2. Then, for all i>1, the set that the mex is being taken over in the definition of # a[i] is a superset of {0,1,2}, and so a[i]>2 for i>1. # # Let C1 be the statement "for every positive integer n>2, there exist positive integers i,j,k such # that a[i]+a[j]+a[k]=2*n". # Let C2 be the statement "for every positive integer n>2, there exist positive integers i,j, both # greater than 1, such that a[i]+a[j]=2*n". # # Claim 2. C1=>C2. # Proof. Let n>2 be an integer. By C1, there exist positive integers i,j,k such that # a[i]+a[j]+a[k]=2*(n+1). But, since 2*(n+1) is even, at least one of a[i], a[j], and a[k] # must be even. Without loss of generality, suppose a[k] is even. By Claim 1, a[k]=2. # Now, a[i] and a[j] must have the same parity. If both were even, then both would equal 2, # so 2*(n+1)=a[i]+a[j]+a[k]=2+2+2=6. But, as n>2, 2*(n+1)>6. Hence, both a[i] and a[j] must be odd. # Again by Claim 1, i>1 and j>1. But then, a[i]+a[j]+2=2*(n+1), so a[i]+a[j]=2*n, with i and j # both positive integers greater than 1. This is C2. # # Claim 3. C2=>C1. # Proof. Let n>2 be an integer. If n=3, then setting i=j=k=1 shows that there exist positive integers # i,j,k such that a[i]+a[j]+a[k]=2*3=2*n. If n>3, then (n-1)>2, so, by C2, there exist positive integers i,j, # both greater than 1, such that a[i]+a[j]=2*(n-1). Thus, letting k=1 shows that there exist positive integers # i,j,k such that a[i]+a[j]+a[k]=a[i]+a[j]+2=2*(n-1)+2=2*n. Thus, C2=>C1. # # Claim 4. C1<=>C2. # Proof. This follows from Claim 2 and Claim 3. # # Claim 5. For every positive integer n, if there exist positive integers i, j, k such that # a[i]+a[j]+a[k]=2*n, then there exist positive integers i', j' such that # a[i']+a[j']=2*n. # Proof. Suppose not. Then, there exists a positive integer n such that there exist positive integers # i, j, k such that a[i]+a[j]+a[k]=2*n, but there do not exist positive integers i', j' such that # a[i']+a[j']=2*n. Take the smallest such n. n must be at least 3, which can be verified by checking # this for n=1 and n=2. Then, n violates C2 but not C1. However, Claim 4 demonstrates # the equivalence of these two claims. Thus, we have reached a contradiction. # # We are now ready to prove the main statement. Suppose it were false, and let n be the smallest # positive integer that, for all positive integers i and j, a[i]+a[j]<>2*n. Again, by checking small # values, n must be at least 3. Thus, n-1 is not a counterexample to the statement, and so there exist # positive integers i,j such that a[i]+a[j]=2*(n-1). But, by setting k=1 so a[k]=2, we find that # a[i]+a[j]+a[k]=2*(n-1)+2=2*n. This shows that here exist positive integers i, j, k such that # a[i]+a[j]+a[k]=2*n. By Claim 5, then, there exist positive integers i', j' such that # a[i']+a[j']=2*n. But this contradicts our assumption that, for all positive integers i and j, a[i]+a[j]<>2*n. # Hence, it follows that for every positive integer n > 1, there exist integers i and j such that a[i]+a[j]=2*n. # # Note: This statement feels similar in nature to Goldbach's conjecture. Perhaps an approach along these lines # could be used to eventually tackle this longstanding problem. This might make an interesting class project for # someone, although I'm busy with my work on finding Somos-like recurrences. ##################################################################################### # Below is a computer program I wrote to better understand the mex function. mex:=proc(S) local i: for i from 0 to max(S)+1 do if S union {i} <> S then return i: fi: od: end: