A curious occurrence of the powers of 4

Here is a curious way in which the powers of 4 turn up in a recursively defined sequence. 


Let the sequence of positive integers a(1), a(2), a(3), ... be defined using the following recursive formula:


a(1) = 1,
a(n) = a(n-1) + Floor(Sqrt(a(n-1)), for n > 1.


The "Floor" function is defined as follows: If x is any real number, then Floor(x) = the largest integer that does not exceed x. For example, Floor(3.1) = 3, Floor (10.7) = 10, Floor(-1.8) = -2, and so on. And, of course, Sqrt simply means "square root". 


I have used these notations because normal mathematical notation does not display properly in a blog.


Using the definition  one can compute the entire sequence recursively. Thus: 


a(2) = 1 + Floor(Sqrt(1)) = 2,
a(3) = 2 + Floor(Sqrt(2)) = 3,
a(4) = 3 + Floor(Sqrt(3)) = 4,
a(5) = 4 + Floor(Sqrt(4)) = 6,


and so on. Continuing this way, we can enumerate the entire sequence (it is particularly easy to do it using a computer). Here are the first 50 terms:


1, 2, 3, 4, 6, 8, 10, 13, 16, 20, 24, 28, 33, 38, 44, 50, 57, 64, 72, 80, 88, 97, 106, 116, 126, 137, 148, 160, 172, 185, 198, 212, 226, 241, 256, 272, 288, 304, 321, 338, 356, 374, 393, 412, 432, 452, 473, 494, 516, 538, ...


From this list, let us sift out just those numbers which are perfect squares; we get the following:


1, 4, 16, 64, 256, ...


Why, these are just the powers of 4. How very curious!


How is one to explain this?


Can we modify the defining rule so that we get some other power sequence (or some other sequence of interest)? Yes we can!  - if we replace Sqrt by CubeRoot we get something equally striking. 


So let us define the sequence of positive integers b(1), b(2), b(3), ...  using the following formula:


b(1) = 1,
b(n) = b(n-1) + Floor(CubeRoot(b(n-1)), for n > 1.


As earlier, we can enumerate the entire sequence, recursively. Here are the first 50 terms:


1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 128, 133, 138, 143, 148, ...


The perfect cubes in this sequence turn out to be these numbers:


1, 8, 64, 512, ...


and these are all the powers of 8.


Many variations are possible, within the same theme. 


Proofs, anyone? Here is a link to one possible line of analysis, written by my friend Ramana: http://ramana.posterous.com/an-intriguing-sequence-contain. Do have a look at it.


I'll write the proofs and post them to my website, later this week.