Home > Algebra, Problem Solving > n-th number which is not a square

n-th number which is not a square


Find a closed form (i.e. an explicit formula in terms of n) for the n-th number which is not a perfect square.

Solution
If we denote a_n as being the n-th number which is not a square, we can see that the following recurence holds:
a_{n+1}=\begin{cases} a_n+1, & n\neq k(k+1), k \in \mathbb{N} \\ a_n+2, & n=k(k+1),\ k \in \mathbb{N} \end{cases}
Further more, we conjecture that a_{k(k+1)}=(k+1)^2-1 and a_{k(k+1)+1}=(k+1)^2+1. We see that for k=1 we have a_2=3 and a_3=5. We begin now to prove our conjecture by induction. Assume that a_{k(k+1)+1}=(k+1)^2+1. Then, using our recurence discovered earlier, we can see that a_{(k+1)(k+2)-1}=a_{k^2+3k+1}=a_{k(k+1)+2k+1}=a_{k(k+1)}+2k+1=k^2+4k+3=(k+2)^2-1, and hence a_{(k+1)(k+2)+1}=(k+2)^2+1. By mathematical induction we can say now that the conjecture is true always. Now, if given n \in \mathbb{N} we can find k \in \mathbb{N} in terms of n such that k(k+1)<n\leq (k+1)(k+2), then we are almost done.

We have the following equivalences:
k(k+1) <  n  \leq (k+1)(k+2) \iff
k^2+k <  n \leq  k^2+3k+2 \iff
4k^2+4k+1  <  4n+1  \leq  4k^2+12k+9 \iff
2k+1  <  \sqrt{4n+1}  \leq  2k+3 \iff
-k-1  \leq  -\frac{\sqrt{4n+1}-1}{2}  <  -k \iff
Therefore k=-1-\left[\frac{1-\sqrt{4n+1}}{2} \right], where [a] is the greatest integer not exceeding a.
To find a_n we proceed as follows:
a_n=a_{k(k+1)+1+n-k(k+1)-1}=a_{k(k+1)+1}+n-1-k(k+1). Replacing k we get a very crowded formula which is correct.

a_n=(\left[ \frac{1-\sqrt{4n+1}}{2} \right])^2+n-(-\left[ \frac{1-\sqrt{4n+1}}{2} \right])(-1-\left[ \frac{1-\sqrt{4n+1}}{2} \right]). Simplyfying, we get
a_n=n-\left[ \frac{1-\sqrt{4n+1}}{2} \right].

Another closed form
\displaystyle n+ \left\lfloor \sqrt{n}+\frac{1}{2}\right\rfloor.

Advertisements
Categories: Algebra, Problem Solving
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: