2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – chairbender Feb 1 '14 at 0:03
  • $\begingroup$ +1 for the instructive explanation and the pattern recognition neurons trigger :-) $\endgroup$ – Markus Scheuer Jun 27 '15 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.