# Solving a recurrence involving floor and square root (Concrete Mathematics 3.28)

I'm working through Concrete Mathematics and having trouble understanding an answer to a problem (as well as what I could've done to come up with the answer).

Problem 3.28 asks:

Solve the recurrence $$a_0 = 1$$ $$a_n = a_{n-1} + \lfloor \sqrt{a_{n-1}}\rfloor (\text{for }n >0)$$

I'm really not sure what to do with this. Chapter 3.3 talks about "Floor/Ceiling Recurrences", but it doesn't really give any general tools or strategies for dealing with them. It just provides two specific examples of problems involving floor/ceiling recurrences.

Looking at the answer at the end it says: "The key observation is that $a_n=m^{2}$ implies $a_{n+2k+1} = (m + k)^2 + m-k$ and $a_{n+2k+2} = (m+k)^2 + 2m$, for $0 \le k \le m$; hence $a_{n+2m+1}=(2m)^2$. The solution can be written in a nice form discovered by Carl Witty: $$a_{n-1}=2^l + \lfloor (\frac{n-l}{2})^2 \rfloor$$ when $2^l + l \le n \lt 2^{l+1} +l+1$

What strategy could I have taken that would've allowed me to make that "key observation"? Furthermore, how does $a_n=m^2$ actually imply that? If I use the recurrence on $a_{n+2k+1}$, I get $$a_{n+2k} + \lfloor \sqrt{a_{n+2k}} \rfloor$$

I can then keep expanding the terms until I get an $a_{n}$ term, and substitute that with $m^2$, but I'm not sure what the other parts of the equation would look like when it has been expanded that much.

...so I can't really come up with a strategy for putting that in terms of m and k (I can't find any techniques the book mentions for doing that), and I haven't really seen something like this in reading the chapters or doing other problems so I don't have an intuitive sense of what to do next.

## 1 Answer

The "key observation" is of course heuristic. Essentially, $a_{n-1}=m^2$ is the simplest case to deal with $\lfloor \sqrt{\ }\rfloor$, so it is worthwhile trying such input first. In fact, we immediately find $m^2\mapsto m^2+m$. What if $a_{n-1}$ is not a square? We can sure write it as $m^2+r$ with $0\le r\le 2m$ (with $r\ge 2m+1$ we'd arrive at $(m+1)^2$). By plugging in we see that $m^2+r\mapsto m^2+m+r$. So $m^2\mapsto m^2+m\mapsto m^2+2m$ takes us almost to the next square in two steps and the next step is $m^2+2m\mapsto m^2+3m=(m+1)^2+(m-1)$. This suggests we rewrite the sequence starting at $a_n=m^2$ like this: \begin{align}m^2&\mapsto m^2+m\\ &\mapsto m^2+2m = (m+1)^2-1\\ &\mapsto (m+\color{red}{1})^2+m-\color{red}1 \\ &\mapsto (m+1)^2+(m+1)+(m-1)=(m+2)^2-3\\ &\mapsto (m+2)^2+(m+1)-3=(m+\color{red}2)^2+m-\color{red}2.\end{align} This should already trigger your pattern recognition neurons that every other entry is of the form $(m+\color{red}k)^2+m-\color{red}k$, more precisely, it looks like $a_{n+2k+1}=(m+k)^2+m-k$. Can we prove this? This clearly holds for $k=0$ as seen above. By induction we see that (provided $0\le k\le m$ so that $m-k\ge0$) \begin{align}(m+\color{red}k)^2+m-\color{red}k&\mapsto (m+k)^2+(m+k)+m-k=(m+k)^2+2m\\ &\mapsto (m+k)^2+(m+k) +2m= (m+\color{red}{k+1})^2+m-\color{red}{(k+1)} \end{align} as required for the claim. So $a_n=m^2$ implies $a_{n+2k+1}=(m+k)^2-m-k$ for $0\le k\le m$ (and, as seen in the intermediate result of the two step computation, $a_{n+2k+2}=(m+k)^2+2m$). Conseqeuntly, $a_{n+2m+1}=(m+m)^2+(m-m)= (2m)^2$.

• It wasn't immediately obvious to me that floor(sqrt(m^2 + r)) = m. But now I see that that is the case since m^2 + r is always less than (m+1)^2, so the square function will return a value between [m,m+1), and the floor function will make it always be just m. – chairbender Feb 1 '14 at 0:03
• +1 for the instructive explanation and the pattern recognition neurons trigger :-) – Markus Scheuer Jun 27 '15 at 5:57