The floor and ceiling functions, denoted [x] and [x] respectively, are functions R ? Z defined by

Now define a function T: N ?N by the recurrence

Find a non-recursive formula for T (n), and prove that your formula is correct

[x] = max{n Z x}, [x] = min{n Z | n x}. T(1) = 1, T(n) = T([n/2])+T([n/2]) for n 2.