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.
Best 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$.