An integer sequence $\{a_{n}\}_{n \ge 1}$ is defined by \[a_{1}=1, \; a_{n+1}=a_{n}+\lfloor \sqrt{a_{n}}\rfloor.\] Show that $a_{n}$ is a square if and only if $n=2^{k}+k-2$ for some $k \in \mathbb{N}$.
Problem
Source:
Tags: floor function, induction, Recursive Sequences
Karlenskij
21.05.2008 17:09
Let's prove that given a $ a_k = m^2$ the next perfect square in the sequence is $ (2m)^2$. Before we prove that for any natural $ s$ we have that: $ a_{(k + 2s + 1)} = (m + s)^2 + (m - s)$. For s=0 $ a_{(k + 1)} = m^2 + m$ we say that it's true for a s:$ a_{(k + 2s + 1)} = (m + s)^2 + (m - s)$ and than: $ a_{(k + 2(s + 1) + 1)} = (m + s)^2 + (m - s) + 2m + 2s = (m + s + 1)^2 + m - (s + 1)$ Now we can see that we have the first perfect square after $ m^2$ when m=s ;so the next perfect square is$ a_{(k + 2m + 1)} = (2m)^2$,infact thanks to the before formula we can see that also for$ a_{(k + 2s + 2)} = (m + s)^2 + (m - s) + m + s < (m + s + 1)^2$.Now with a very simple induction we know that starting from $ a_1 = 1$ all the perfect squares of the sequnce are the perfect squares of all the perfect powers of 2.Now let's prove that$ 2^{(k - 1)}^2 = a_{(2^k + k - 2)}$ for any k.$ a_{(2 + 1 - 2)} = 2^0$.We say that $ a_{(2^k + k - 2)} = 2^{(k - 1)}^2$ and we see that for what we said before: $ a_{(2^k + k - 2 + 2^{(k - 1)}2 + 1)} = (2(2^{(k - 1)})^2 = (2{}^k){}^2 = a_{(2^{(k + 1)} + (k + 1) - 2)}$ that prove the thesis.