Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to solve the recurrence:

$A_0=1$

$A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor,\text{ for } n > 0$

Its obvious that

$A_n=m^2 \implies A_{n+1}=m^2+m$

however my book's solution states that the key insight is to realize:

$A_n=m^2 \implies A_{n+2k+1}=(m+k)^2+m-k\text{, for }0 \le k \le m$

and

$A_n=m^2 \implies A_{n+2k+2}=(m+k)^2+2m\text{, for }0 \le k \le m$

What method or line of thinking would have lead me to this?

This is exercise 3.28 from Concrete Mathematics.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I'll use $r(x) = \lfloor \sqrt{x}\rfloor$ throughout.

Warm Up Here's some stuff we'll use freely in the next section. It's motivated by the next section though.

What's the floor of the square root of $m^2+7m+5$? You can read it off this table:

$$\begin{array}{|c|c|c|} \hline m+k & m^2 + 2km + k^2 \\ \hline m+1 & m^2 + 2m + 1 \\ m+2 & m^2 + 4m + 4 \\ m+3 & m^2 + 6m + 9 \\ m+4 & m^2 + 8m + 16 \\ m+5 & m^2 + 10m + 25 \\ m+6 & m^2 + 12m + 36 \\ m+7 & m^2 + 14m + 49 \\ \hline \end{array}$$

It must be $m+3$.. but we do need $2k < m$ to use this table. It's easy to find counterexamples (e.g. $r(3^2+7\cdot 3+5)=5$).


Using this we can push your idea of starting with a generic $A_n = m^2$ much further and see the recurrence:

$$\begin{array}{|l|l|} \hline A_n & r(A_n) \\ \hline m^2 & m \\ m^2 + m & m \\ m^2 + 2m & m \\ m^2 + 3m & m + 1 \\ m^2 + 4m + 1 & m + 1 \\ m^2 + 5m + 2 & m + 2 \\ m^2 + 6m + 4 & m + 2 \\ m^2 + 8m + 6 & m + 3 \\ \end{array}$$

of course with the same caveat as before.

To try to formulate the pattern in this table (in order to prove it by induction) we get exactly the key insight you mentioned.

share|improve this answer
    
Maybe it helps if you see both equalities: $(m+k)^2+m-k+(m+k)=(m+k)^2+2m$ and $(m+k)^2+2m+(m+k)=(m+(k+1))^2+m-(k+1)$ –  ama Mar 12 '13 at 9:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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