PFTB 16.18
by Wolstenholme, Aug 8, 2014, 2:29 AM
Let 
be a set of positive integers such that for any
, there is a positive
integer
such that 
. Prove
that contains numbers with arbitrarily large digit sum.
Proof:
Given an integer
, I will show that there exists an element in 
with digit sum larger than . From now on, let 
. By Lemma 16.3 from this chapter, we have that any multiple of 
has digit sum at least 
so it suffices to find an 
such that 
for all 
.
Now consider the sequence defined by
for all . This recurrence relation has characteristic polynomial 
whose roots are 
. Therefore this sequence has closed form 
for some 
. Using the fact that 
and 
we find that 
.
Now taking the sequence modulo we have that the recurrence relation becomes 
and so 
for all . But since 
we have that 
and so 
for all .
Since clearly
we can take 
and so we are done.
be a set of positive integers such that for any
, there is a positiveinteger
such that 
. Provethat
contains numbers with arbitrarily large digit sum.Proof:
Given an integer
, I will show that there exists an element in 
with digit sum larger than . From now on, let 
. By Lemma 16.3 from this chapter, we have that any multiple of 
has digit sum at least 
so it suffices to find an 
such that 
for all 
.Now consider the sequence defined by
for all . This recurrence relation has characteristic polynomial 
whose roots are 
. Therefore this sequence has closed form 
for some 
. Using the fact that 
and 
we find that 
.Now taking the sequence modulo
we have that the recurrence relation becomes 
and so 
for all . But since 
we have that 
and so 
for all .Since clearly
we can take 
and so we are done.This post has been edited 1 time. Last edited by Wolstenholme, Aug 8, 2014, 2:29 AM
August 2016
June 2016