Saturday, October 10, 2015

Sequence theorem

Suppose you have an infinite natural number sequence that starts with 1, 2 and except for 2 every number in the sequence is more than it's predecessor but less than double it's predecessor...

Every natural number N can be written as the sum of no more than log(N) distinct numbers from the sequence, greedily.
Greedily meaning you pick the largest element from the sequence smaller than N first, then after subtracting that the next largest and so on...

First that every natural number can be written as the sum of distinct numbers from the sequence:

Suppose you have the first number N that can't be written as the sum of distinct numbers from the sequence, subtract the largest number from the sequence less than N, called S, N-S != S because that would mean that N = 2*S and we know there would have to be a number from the sequence between S and 2*S that we would have subtracted instead of S, because every number in our sequence is less than double it's predecessor... So N-S will yield a different number than S, S2 which is either in the sequence or not. If it is than we are done because N=S+S2 which is the sum of distinct numbers from the sequence, a contradiction. If it's not in the sequence we know that it can be written as the sum of distinct numbers from the sequence because N was assumed to be the smallest number not able to be written that way. Then N = S + (some smaller distinct numbers from the sequence than S), another contradiction. Thus there is no first number that can't be written as the sum of distinct numbers from the sequence, or all natural numbers can be written as such...

The number of numbers used from the sequence to sum to N must be less than log(N) because using the method above N-S, subtracting the largest number from the sequence less than N, is always less than S so you've more than halved N, and you can only halve N log(N) times to reach 1.

So there are a lot of series that fit this description like the Fibonacci numbers without 1:
1,2,3,5,8,13...

Or the primes plus 1:
1,2,3,5,7,11,13...