Let m be the smallest integer greater than (√3 + 1)2n. Show that m is divisible by 2n+1.
Solution
This is a fairly well-known problem. (√3 - 1) < 1 and (we will show) (√3 + 1)2n + (√3 - 1)2n (*) is an integer. Hence it must be the required integer.
But it is easy to check that (*) is the solution of a recurrence relation, in fact the relation un = 8un-1 - 4un-2, u0 = 2, u1 = 8. That establishes that (*) is an integer, and a trivial induction shows that (*) is divisible by 2n+1.
© John Scholes
jscholes@kalva.demon.co.uk
14 Dec 1999