Problem: T ( 1 ) = 2 T ( 1 ) = 2 T ( n + 1 ) = 2 T ( n ) T ( n + 1 ) = 2 T ( n ) n ≥ 1 n ≥ 1 A = ( T ( 2009 ) ) T ( 2009 ) A = ( T ( 2 0 0 9 ) ) T ( 2 0 0 9 ) B = ( T ( 2009 ) ) A B = ( T ( 2 0 0 9 ) ) A k k
2 2 2 … 2 ⏟ k times B k times log 2 log 2 log 2 … log 2 B
is defined?
Answer Choices:
A. 2009 2 0 0 9 2010 2 0 1 0 2011 2 0 1 1 2012 2 0 1 2 2013 2 0 1 3 Solution:
Define the k k 2 1 x = 2 x log 2 1 x = log 2 x 2 k + 1 x = 2 ( 2 k x ) log 2 k + 1 x = log 2 ( log 2 k x ) k ≥ 1 k ≥ 1 2 T ( n + 1 ) = T ( n ) log 2 T ( n + 1 ) = T ( n ) n ≥ 1 n ≥ 1 2 A = T ( 2009 ) 2 T ( 2009 ) = T ( 2009 ) T ( 2008 ) log 2 A = T ( 2 0 0 9 ) log 2 T ( 2 0 0 9 ) = T ( 2 0 0 9 ) T ( 2 0 0 8 ) 2 B = A 2 T ( 2009 ) = A ⋅ T ( 2008 ) log 2 B = A log 2 T ( 2 0 0 9 ) = A ⋅ T ( 2 0 0 8 ) 2 2 B = 2 A + 2 T ( 2008 ) = log 2 2 B = log 2 A + log 2 T ( 2 0 0 8 ) = T ( 2009 ) T ( 2008 ) + T ( 2007 ) T ( 2 0 0 9 ) T ( 2 0 0 8 ) + T ( 2 0 0 7 )
2 3 B > 2 ( T ( 2009 ) T ( 2008 ) ) > 2 T ( 2009 ) = T ( 2008 ) log 2 3 B > log 2 ( T ( 2 0 0 9 ) T ( 2 0 0 8 ) ) > log 2 T ( 2 0 0 9 ) = T ( 2 0 0 8 )
and recursively for k ≥ 1 k ≥ 1
2 k + 3 B > T ( 2008 − k ) log 2 k + 3 B > T ( 2 0 0 8 − k )
In particular 2 2010 B > T ( 1 ) = 2 log 2 2 0 1 0 B > T ( 1 ) = 2 2 2012 B > 0 log 2 2 0 1 2 B > 0 2 2013 B log 2 2 0 1 3 B
On the other hand, because T ( 2007 ) < T ( 2008 ) T ( 2009 ) T ( 2 0 0 7 ) < T ( 2 0 0 8 ) T ( 2 0 0 9 ) 1 + T ( 2007 ) < 1 + T ( 2 0 0 7 ) < T ( 2008 ) T ( 2 0 0 8 )
2 3 B < 2 ( 2 T ( 2008 ) T ( 2009 ) ) = 1 + T ( 2007 ) + T ( 2008 ) < 2 T ( 2008 ) and 2 4 B < 2 ( 2 T ( 2008 ) ) = 1 + T ( 2007 ) < T ( 2008 ) log 2 3 B < log 2 ( 2 T ( 2 0 0 8 ) T ( 2 0 0 9 ) ) = 1 + T ( 2 0 0 7 ) + T ( 2 0 0 8 ) < 2 T ( 2 0 0 8 ) and log 2 4 B < log 2 ( 2 T ( 2 0 0 8 ) ) = 1 + T ( 2 0 0 7 ) < T ( 2 0 0 8 )
Applying 2 log 2 k ≥ 1 k ≥ 1
2 4 + k B < T ( 2008 − k ) log 2 4 + k B < T ( 2 0 0 8 − k )
In particular 2 2011 B < T ( 1 ) = 2 log 2 2 0 1 1 B < T ( 1 ) = 2 2 2013 B < 0 log 2 2 0 1 3 B < 0 2 2014 B log 2 2 0 1 4 B
The problems on this page are the property of the MAA's American Mathematics Competitions