2
$\begingroup$

I think my solution must be wrong because it's way too simple and it disagrees with other solutions I have seen online. But I really can't figure out where the mistake is.

Define a positive integer $n$ to be squarish if either $n$ is itself a perfect square or the distance from $n$ to the nearest perfect square is a perfect square. For example, $2016$ is squarish, because the nearest perfect square to $2016$ is $45^2=2025$ and $2025-2016=9$ is a perfect square. (Of the positive integers between $1$ and $10,$ only $6$ and $7$ are not squarish.)

For a positive integer $N,$ let $S(N)$ be the number of squarish integers between $1$ and $N,$ inclusive. Find positive constants $\alpha$ and $\beta$ such that

$$\lim_{N\to\infty}\frac{S(N)}{N^{\alpha}}=\beta,$$

or show that no such constants exist.

Since $S(N)$ just counts some of the numbers between $1$ and $N$, we have $ 0 \le S(N) \le N$ for any $N$. So for any $N$,

$$\dfrac {0}{N^{\alpha}} \le \frac{S(N)}{N^{\alpha}} \le \dfrac {N}{N^{\alpha}}$$

$$0 \le \frac{S(N)}{N^{\alpha}} \le \dfrac {1}{N^{\alpha-1}}$$

Let $\alpha = 2$

$$0 \le \frac{S(N)}{N^{2}} \le \dfrac {1}{N}$$

By the Squeeze (Sandwich?) Theorem,

$$\lim_{N\to\infty}\frac{S(N)}{N^{2}}=0$$

So $\alpha = 2$, $\beta = 0$ (or $\alpha=$ any number $>2, \beta = 0$)

$\endgroup$
  • 4
    $\begingroup$ You've ignored the requirement that $\beta>0$. Given that those constants are asked to be positive, what they're really trying to get you to do is to say that $S(n)\approx\beta N^{\alpha}$ for some $\alpha,\beta>0$; they're asking you to find the asymptotically most important term in describing the sequence's behavior. $\endgroup$ – Nick Peterson Dec 5 '16 at 15:01
  • $\begingroup$ @NickPeterson Ouch I completely missed that the constants have to be positive! $\endgroup$ – Ovi Dec 5 '16 at 15:02
  • $\begingroup$ @amWhy I don't see any requirement for $\alpha$ being a squarish number. $\endgroup$ – Ovi Dec 5 '16 at 15:03
  • $\begingroup$ @amWhy: The nearest perfect square to $2$ is $1$, which is distant from $2$ by a perfect square ($1=1^2$), so $2$ is squarish. $\endgroup$ – Steve Kass Dec 5 '16 at 15:05
  • $\begingroup$ Got it Steve, I was thinking in term of being with respect to the "next" perfect square $\endgroup$ – Namaste Dec 5 '16 at 15:07
4
$\begingroup$

For a positive integer $m$, we say that $n\in\mathbb{Z}_{>0}$ is its center if $n^2$ is the closest perfect square to $m$, in which case, we say that $m$ is a neighbor of $n$. First, it is easy to see that, for any positive integer $m$ with center $n$, $$n^2-n\leq m\leq n^2+n\,.$$ Note that a positive integer $m$ is squarish if and only if $$m=n^2\pm k^2\text{ for some }k\in\big\{0,1,2,\ldots,\lfloor\sqrt{n}\rfloor\big\}\,,$$ where $n$ is the center of $m$.

Now, let $a_n$ denote the number of squarish neighbors of a given positive integer $n$. From the result above, we see that $$a_1=2\text{ and }a_n=2\,\lfloor\sqrt{n}\rfloor+1\text{ for each }n\in\mathbb{Z}_{>1}\,.$$ Thus, $$S(n^2+n)= \sum_{r=1}^n\,a_r=-1+\sum_{r=1}^n\,\big(2\,\lfloor \sqrt{r}\rfloor+1\big)\tag{*}$$ for every positive integer $n$. That is, $$-1+\sum_{r=1}^n\,(2\sqrt{r}-1)<S(n^2+n)\leq -1+\sum_{r=1}^n\,(2\sqrt{r}+1)\,.$$

Using Bernoulli's Inequality, we have $$\left(1+\frac{1}{j}\right)^{\frac{3}{2}}\geq 1+\frac{3}{2j}\text{ for all }j\in\mathbb{Z}_{>0}\,.$$ That is, $$\sqrt{j}\leq \frac{2}{3}\,\left((j+1)^{\frac{3}{2}}-j^{\frac{3}{2}}\right)\,.$$ Likewise, $$\left(1-\frac{1}{j}\right)^{\frac{3}{2}}\geq 1-\frac{3}{2j}\text{ for all }j\in\mathbb{Z}_{>0}\,.$$ This implies $$\sqrt{j}\geq \frac{2}{3}\,\left(j^{\frac{3}{2}}-(j-1)^{\frac{3}{2}}\right)\,.$$

From (*), we get that $$\frac{4}{3}\,n^{\frac{3}{2}}-n-1< S(n^2+n)\leq \frac{4}{3}\,\left((n+1)^{\frac{3}{2}}-1\right)+n-1\,.$$ Thus, for any positive integer $N$ with center $n$, we have $n^2-n\leq N$, so that $$n\leq \sqrt{N+\frac{1}{4}}+\frac{1}{2}<\sqrt{N}+1$$ and $$S(N)\leq S(n^2+n)<\frac{4}{3}\,\left(\left(\sqrt{N}+2\right)^{\frac{3}{2}}-1\right)+\sqrt{N}$$ for all integers $N>0$. Similarly, $N\leq n^2+n$ implies that $$n\geq \sqrt{N+\frac{1}{4}}-\frac{1}{2}>\sqrt{N}-1$$ and $$S(N)\geq S\big((n-1)^2+(n-1)\big)>\frac{4}{3}\,\left(\sqrt{N}-2\right)^{\frac{3}{2}}-\sqrt{N}-1\,,$$ for all integers $N\geq 4$.

Consequently, we have proven that, for all integers $N\geq 4$, $$\frac{4}{3}\,\left(\sqrt{N}-2\right)^{\frac{3}{2}}-\sqrt{N}-1< S(N)< \frac{4}{3}\,\left(\left(\sqrt{N}+2\right)^{\frac{3}{2}}-1\right)+\sqrt{N}\,.$$ Ergo, $$\frac{4}{3}\,\left(1-\frac{2}{\sqrt{N}}\right)^{\frac{3}{2}}-\frac{1}{N^{\frac14}}-\frac{1}{N^{\frac{3}{4}}}< \frac{S(N)}{N^{\frac{3}{4}}}< \frac{4}{3}\,\left(\left(1+\frac{2}{\sqrt{N}}\right)^{\frac{3}{2}}-\frac{1}{N^{\frac34}}\right)+\frac{1}{N^{\frac{1}{4}}}\,.$$ By the Squeeze Theorem, $$\lim_{N\to\infty}\,\frac{S(N)}{N^{\frac{3}{4}}}=\frac{4}{3}\,,$$ whence $\alpha=\dfrac{3}{4}$ and $\beta=\dfrac{4}{3}$.

$\endgroup$

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.