Let $\beta^2=\alpha$, which is also greater than one and irrational. Let $\beta^n=m-e=m_n-e_n$, with $m\in\mathbb{Z}$ and $e\in(0,1)$ (note that $e$ can't be zero by irrationality). Then, $\alpha^n=\beta^{2n}=m^2-2me+e^2$ which belongs to $((m-1)^2,m^2)$, which means that for $n$ (and thus $m$) big enough the perfect square in the definition must be $m$ (otherwise another big enough perfect square minus $k$ wouldn't fit in the interval). So, we must have $\lfloor m^2-2me+e^2\rfloor=m^2-\lceil 2me-e^2\rceil=m^2-k$, which implies $\lceil 2me-e^2\rceil=k$ for all big $k$. This in turn implies $2me\leq k+1+e^2\leq k+2$ and so $2\beta^ne\leq 2me\leq k+2$. Therefore, as $n$ goes to infinity and $m$ as well, $e$ must go to zero (in particular it will always be less than $\frac 12$ after some point). Now, defining $||x||=\inf_{t\in \mathbb{Z}}|x-k|$, we have that for big enough $n$ $e_n=||\beta^n||$. Therefore, we can reframe our inequality as $||\beta^n||\leq\frac{k+2}{2}\frac{1}{\beta^n}$. Since this sequence must be square summable (its infinite sum of squares converges), it is known that $\beta$ must be a Pisot–Vijayaraghavan number (for short PV number); in other words, by considering the minimal polynomial $p(x)\mathbb{Z}[x]$(this means that $\beta$ is also an algebraic integer) of $\beta$, all other roots $\beta_2,...,\beta_d$ are (possibly complex) numbers with absolute value $<1$ (assume wlog $|\beta_d|\leq |\beta_{d-1}|\leq \cdots \leq |\beta_2|<1<\beta_1=\beta$). Since $p(x)$ is a monic integer polynomial, the sum of powers of its roots is always an integer, so that in fact for big $n$ $||\beta^n||=|\beta_2^n+\cdots +\beta_d^n|$. Now assume that the degree $d$ of $\beta$ is larger than $2$. Since $|\beta_1\cdots \beta_d$ is a positive integer $\geq 1$, it follows that $|\beta\beta_2|>1$ (because $d>2$ and $|\beta_3\cdots \beta_d|<1$). Therefore $m^2=(\beta+\beta_2+\cdots +\beta_d)^n=\beta^{2n}+2(\beta\beta_2)^n+O(|\beta\beta_2|^n)=\beta^{2n}-E(n)$. In fact, even if there is a $t>2$ such that $|\beta_2|=|\beta_3|=\cdots =|\beta_t|$, there exists an $n$ such that the arguments of $\beta_2^n,...,\beta_t^n$ are all approximately $0$ (or $2\pi$), in a way that there are infinitely many $n$ such that the error term is a constant times $|\beta\beta_2|^n$; therefore we might as well pick the case in which $t=2$, since otherwise we make the make the same reasoning for all the infinitely many $n$ such that $\max_{i=2,...,t}|arg (\beta_i^n)$ is less then a fixed constant $\epsilon<\pi/2$, say $0.1$; in yet other terms there exists infinitely many $n$ such that the error term is of absolute value $c_1|\beta\beta_2|^n\leq |E(n)|<c_2|\beta\beta_2|^n$, with $0<c_1<c_2$. However, since we must have that $E(n)$ differs from $k$ of at most by one, but this is contradicted by the fact that $\limsup_{n\rightarrow}E(n)=\infty$ because $|\beta\beta_2|>1$ (also note that the fact that $|\beta\beta_2|^n=o(\beta^n)=o(m)$ confirms the fact that $\beta^{2n}$ lies in $((m-1)^2,m^2)$. Therefore, $\beta$ is an algebraic integer of degree $2$ (it can't be of degree $1$ because it would be an integer). By the same reasoning as before, we must have $|\beta\beta_2|\leq 1$, but this can only happen if $\beta\beta_2=\pm 1$, so we now have only two cases(from now on rename $\beta_2$ to $\bar{\beta}$): I) $\beta\bar{\beta}=-1$. In this case we have $\beta^{2n}+\bar{\beta}^{2n}-2=m^2$ which implies $\lfloor \beta^{2n}\rfloor =m^2+2-\lceil \bar{\beta}^{2n}\rceil \geq m^2+1$ which is a contradiction II) $\beta\bar{\beta}=+1$. By a similar calculation we have $$\lfloor \alpha^n\rfloor=\lfloor \beta^{2n}\rfloor=m^2-2-\lceil \bar{\beta}^{2n}\rceil=m^2-3$$for all $n$. Therefore $k$ can only be $3$ which can be achieved if (and only if) $\beta^2-t\beta+1=0$ so that $\beta=\frac{t+\sqrt{t^2-4}}{2}$ with $|t|$ being an integer greater than $2$.

First of all, the following solution is not mine. It is nothing more than the translation of a solution originally written in Portuguese which avoids the (extremely interesting and somewhat exotic) results from algebraic number theory used above, since they are not part of a solution expected from most high school students. Answer: $k=3$ is the only possibility (example provided at the end). Let $\lfloor \alpha^n\rfloor = m_n^2 - k$. So, letting $m_n = \alpha^{n/2}+r_n$, $\lfloor \alpha^n \rfloor + k = m_n^2 = \alpha^n + 2\alpha^{n/2}r_n + r_n^2$, and we conclude that $0 < r_n = O(\alpha^{-n/2})$. If we replace $n$ by $2n$ we get, for all big $n$, $$\alpha^n < m_{2n} = \alpha^n + O(\alpha^{-n})\implies \lfloor \alpha^n\rfloor = m_{2n} - 1 = m_n^2 - k\iff m_{2n} = m_n^2 - c,\quad c=k-1.$$ Now, from $m_{2n} = \alpha^n + O(\alpha^{-n})\implies m_n^2 = c + \alpha^n + O(\alpha^{-n})$ \begin{align*} m_n = \alpha^{n/2} + r_n &\implies m_n^2 = \alpha^n + 2\alpha^{n/2}r_n + r_n^2\implies \alpha^n + 2\alpha^{n/2}r_n + r_n^2 = c+\alpha^n + O(\alpha^{-n})\\ &\iff 2\alpha^{n/2}r_n + r_n^2 = c + O(\alpha^{-n})\implies r_n = -r_n^2\alpha^{-n/2} + \frac c2\cdot\alpha^{-n/2} + O(\alpha^{-3n/2}). \end{align*} As$-r_n^2\alpha^{-n/2} = O(\alpha^{-n-n/2})$, $$r_n = \frac c2\cdot \alpha^{-n/2} + O(\alpha^{-3n/2})\implies m_n = \alpha^{n/2} + \frac c2\cdot \alpha^{-n/2} + O(\alpha^{-3n/2})$$ Define now $\lambda = \alpha^{1/2} + \alpha^{-1/2}$. Comparing the previous equation for $m_{n-1}$, $m_n$ and $m_{n+1}$, we get \begin{align*} m_{n+1} &= \alpha^{(n+1)/2} + \frac c2\cdot\alpha^{-(n+1)/2} + O(\alpha^{-3n/2})\\ m_{n-1} &= \alpha^{(n-1)/2} + \frac c2\cdot\alpha^{-(n-1)/2} + O(\alpha^{-3n/2})\\ m_n &= \alpha^{n/2} + \frac c2\cdot\alpha^{-n/2} + O(\alpha^{-3n/2}) \end{align*} Observing that $x_k = \alpha^{k/2} + \frac c2\cdot \alpha^{-k/2}$ satisfies the recursion $x_{k+1} + x_{k-1} = \lambda x_k$, we have $$m_{n+1} + m_{n-1} = \lambda m_n + O(\alpha^{-3n/2}).$$ Recalling that $m_n = \alpha^{n/2}+O(1)$, we have $$\frac{m_{n+1}+m_{n-1}}{m_n} = \lambda + O(\alpha^{-2n}).$$ Shifting $n$ by $1$ does not change $O(\alpha^{-2n})$. Therefore $$\frac{m_{n+1}+m_{n-1}}{m_n} = \frac{m_{n+2}+m_n}{m_{n+1}} = \lambda + O(\alpha^{-2n})$$Observe that both numbers are rational. If they were different, we would get $$\left|\frac{m_{n+1}+m_{n-1}}{m_n} - \frac{m_{n+2}+m_n}{m_{n+1}}\right| \ge \frac1{m_nm_{n+1}} = (1+o(1))\alpha^{-n/2-(n+1)/2} = (1+o(1))\alpha^{-n-1/2}\ne O(\alpha^{-2n}).$$ Thus, the two fractions are equal for all sufficiently large $n$, i.e., $\frac{m_{n+1}+m_{n-1}}{m_n}$ is constant for all big $n$. As this ratio is $\lambda+o(1)$, we get $$\frac{m_{n+1}+m_{n-1}}{m_n} = \lambda\quad\text{for all sufficiently large }n\text{.}$$ From here it follows $\alpha^{1/2}+\alpha^{-1/2} = \lambda = \frac{m_{n+1}+m_{n-1}}{m_n}$ is rational, and as the sequence $(m_n)$ satisfies the recursion $m_{n+1}=\lambda m_n-m_{n-1}$ for all big $n$, there are constants $A$ and $B$ such that $m_n=A\alpha^{n/2}+B\alpha^{-n/2}$ for all big $n$. From $m_n = \alpha^{n/2} + \frac c2\cdot \alpha^{-n/2} + O(\alpha^{-3n/2})$ it follows that $A=1$ and $B=\frac c2$, and therefore $m_n = \alpha^{n/2} + \frac c2\cdot \alpha^{-n/2}$ for all big $n$. Squaring the previous relation, we are left with $m_n^2=\alpha^{n} +c+ \left(\frac c2\right)^2\cdot \alpha^{-n}$, from which we get $m_{2n}=m_n^2-c=\alpha^{n}+(\frac c2)^2\cdot \alpha^{-n}$, and comparing with the formula obtained for $m_n$ (change $n$ for $2n$), the conclusion is that $\frac c2=\left(\frac c2\right)^2$, implying either $c=2$ or $c=0$. If it was the case that $c=0$, we would have $m_n = \alpha^{n/2}$ for all big $n$, and then $m_{2n}=\alpha^n$, implying $m_n^2-k=\lfloor \alpha^n \rfloor=m_{2n}=m_n^2-c$, contradiction!, since $c=k-1$. Therefore $c=2$ and $k=c+1=3$. There are several examples for $k=3$. One of them is choosing $\alpha = \varphi^2 = \frac{3+\sqrt 5}2$, where $\varphi = \frac{1+\sqrt5}2$ is the golden ratio, and since $\alpha^{-1} < 1$, $$\lfloor \alpha^n\rfloor = \varphi^{2n} + \varphi^{-2n} - 1 = (\varphi^n + \varphi^{-n})^2 - 3 = L_n^2 - 3,$$where $L_n = \varphi^n + \varphi^{-n}$ is the $n$-th Lucas number ($L_0=2$, $L_1=1$ and $L_n=L_{n-1}+L_{n-2}$, $n\ge 2$).

bruckner wrote: we conclude that $0 < r_n = O(\alpha^{-n/2})$. . Why?

Edit: removed incorrect post.

@above: I'm afraid you haven't read the article properly. The first theorem in the section "Diophantine properties" is used ( with the condition $\sum_1^\infty ||\lambda \alpha^n||^2<\infty$) and not the second one. The thing you mention about algebraic or not has to do with the more general statement in the second theorem. But it's not that theorem that cadaeibf uses. @below: no worries.

I see, sorry for the confusion. Thank you for the clarification.

Solution from Twitch Solves ISL: The answer is $k=3$ only. Construction. Consider the integer sequence \[ x_n \coloneqq \left( \frac{3 + \sqrt 5}{2} \right)^n + \left( \frac{3 - \sqrt 5}{2} \right)^n \]defined by $x_0 = 2$, $x_1 = 3$, $x_2 = 7$, $x_{n+2} = 3x_{n+1} - x_n$, and so on. Then we have \[ x_n^2 \coloneqq \left( \frac{14 + 6\sqrt 5}{4} \right)^n + \left( \frac{14 - 6\sqrt 5}{4} \right)^n + 2. \]so \[ \left\lfloor \left( \frac{14+6\sqrt5}{4} \right)^n \right\rfloor = x_n^2 - 3 \]holds for every $n$ (since $0 < \frac{14-6\sqrt5}{4} < 1$). This provides $\alpha = \frac{14+6\sqrt5}{4}$ as an example. Proof that $k=3$ is the only one possible. Throughout this solution, the big $O$ notation treats $\alpha$ and $k$ as $O(1)$. For each $n > N$, we introduce the notation \[ \alpha^n = x_n^2 - k + \varepsilon_n \qquad x_n \in {\mathbb N}, 0 < \varepsilon_n < 1. \]In particular, $x_n = \sqrt{\alpha^n + O(1)} = \alpha^{n/2} + O(\alpha^{-n/2})$. We make the following assertion. Claim: We have $1 - \varepsilon_n = O(\alpha^{-n})$ and $x_n^2 = x_{2n} + (k-1)$. Proof. Note that \begin{align*} \alpha^{2n} &= x_{2n}^2 - k + \varepsilon_{2n} \\ \implies \left( \alpha^n - x_{2n} \right) \left( \alpha^n + x_{2n} \right) &= -k + \varepsilon_{2n} \\ \implies \left( x_n^2 - x_{2n} - k + \varepsilon_n \right) (\alpha+x_{2n}) &= \varepsilon_{2n} - k \end{align*}Rearrange this to \[ x_n^2 - x_{2n} - k = -\varepsilon_n - \frac{k-\varepsilon_{2n}}{\alpha^n + x_{2n}}. \]The right-hand side is an integer strictly between $-2$ and $0$, so it's $-1$. So we get both the equality of the main terms \[ x_n^2 = x_{2n} + (k-1) \]and the estimate on the error term \[ 1 - \varepsilon_n = \frac{k - \varepsilon_{2n}}{\alpha^n+ x_{2n}} = \frac{O(1)}{2\alpha^n + O(\alpha^{-n})} = O(\alpha^{-n}). \]$\blacksquare$ In the main equation, replacing $x_n^2$ with $x_{2n} + (k-1)$ gives \[ \alpha^n = x_{2n} - (1 - \varepsilon_n) = x_{2n} - \frac{k-\varepsilon_{2n}}{\alpha^n+x_{2n}}. \]The fraction equals $\frac{k-1 + O(\alpha^{-n})}{2\alpha^n + O(\alpha^{-n})}$ and so we get \[ x_{2n} = \alpha^n + \frac{\frac{k-1}{2}}{\alpha^n} + O(\alpha^{-2n}). \]Multiplying both sides by $\alpha + \frac{1}{\alpha}$ gives \begin{align*} \left( \alpha + \frac{1}{\alpha} \right) x_{2n} &= \alpha^{n+1} + \frac{\frac{k-1}{2}}{\alpha^{n+1}} + \alpha^{n-1} + \frac{\frac{k-1}{2}}{\alpha^{n-1}} + O(\alpha^{-2n}) \\ &= x_{2n+2} + x_{2n-2} + O(\alpha^{-2n}). \end{align*}Hence \[ \frac{x_{2n+2}+x_{2n-2}}{x_{2n}} = \alpha + \frac{1}{\alpha} + O(\alpha^{-3n}). \]The critical claim is that the error term is actually zero exactly: Claim: The equation \[ \frac{x_{2n+2}+x_{2n-2}}{x_{2n}} = \alpha + \frac{1}{\alpha} \]holds for large enough $n$. Proof. Notice that $\frac{x_{2n+2}+x_{2n-2}}{x_{2n}} - \frac{x_{2n}+x_{2n-4}}{x_{2n-2}}$ is the difference of two terms which are $O(\alpha^{-3n})$. However, it's the difference of two rational numebrs whose denominators are each $\Theta(\alpha^n)$, ergo their difference is at least $1/O(\alpha^{2n})$. This is too large, so the error terms between consecutive fractions must be constant. Since it also decays to zero, it must be eventually zero.,. $\blacksquare$ From this, we have a bona fide linear recurrence with exact equalities \[ x_{2n} = \lambda_+ \cdot \alpha^n + \lambda_- \cdot \alpha^{-n} \]for some constants $\lambda_+$ and $\lambda_-$; but actually $\lambda_+ = 1$ and $\lambda_- = \frac{k-1}{2}$ to match our earlier equation for $x_{2n}$; that is, we have exactly \[ x_{2n} = \alpha^n + \frac{\frac{k-1}{2}}{\alpha^n}. \]On the other hand, we are supposed to have $x_{2n}^2 = x_{4n} + (k-1)$ and comparing these two forces $\frac{k-1}{2} = 1$, so $k = 3$.

Am i making a mistake coz this sol seems much simpler than others,[though i havent read]. We prove any $k \neq 3$ wont work. Assume the contrary. $\lfloor \alpha^{2n} \rfloor = \lfloor \alpha^{2n}+\frac{1}{\alpha^{2n}} \rfloor + \mathcal{O}(1)=(\alpha^n+\frac{1}{\alpha^n})^2+\mathcal{O}(1)$ For large $n$ We know $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor )^{2}-k \leq \alpha^{2n} + \frac{1}{\alpha^{2n}}+(2-k)$ so $\frac{1}{\alpha^{2n}}+(3-k) > 0$ setting $n$ large we know $ k \leq 3$. Case 1: $k=2$ This would force $\lfloor \alpha^{2n} \rfloor =(\lfloor \alpha^{n} + \frac{1}{\alpha^n} \rfloor)^2-1$ with some more bounding its easy to see $\lfloor \alpha^{n}+ \frac{1}{\alpha^n} \rfloor = \lfloor \alpha^n \rfloor +1$ for large $n$ This also means $\{\alpha^n\}$ gets arbitarily close to $1$ So $\lfloor \alpha^{2n} \rfloor=(\lfloor \alpha^{n} \rfloor +1)^2-2= $ so $\lfloor { \alpha^{n} + \frac{1}{\alpha^{n}}} \rfloor^2= \lfloor (\alpha^{n}+\frac{1}{\alpha^{n}})^2 \rfloor-1$ Use this to show $\{\alpha^{n}+\frac{1}{\alpha^{n}}\}$ can grow arbitarily large but its bounded by 1 causing contradiction or it would be integral always which is an easy case to deal with For $k=1$ a similar techinique works . For $k=3$ we can easily provide a construction By letting $\alpha$ be the solution of $\alpha+\frac{1}{\alpha}=3$

idkk wrote: We know $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor )^{2}-k $ why?

This post does not seem correct, namely because $(\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor )^{2} - \left(\alpha^{n}+\frac{1}{\alpha^{n}}\right)^2 \ne O(1)$.

YaoAOPS wrote: This post does not seem correct, namely because $(\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor )^{2} - \left(\alpha^{n}+\frac{1}{\alpha^{n}}\right)^2 \ne O(1)$. Oops ya srry i messed up the latex it should be $\lfloor (\alpha^{2n}+\frac{1}{\alpha^{2n}}) \rfloor = (\lfloor \alpha^{n} + \frac{1}{\alpha^n} \rfloor)^2-1$ [by adding 1 on both sides] Followed by adding 2 on both sides

zhihanpeng2.0 wrote: idkk wrote: We know $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor )^{2}-k $ why? Otherwise $\lfloor \alpha^{2n} \rfloor \leq (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor -1)^{2}-k $ For large enough $n$ the error created will be too much , as $\alpha^{n}+\frac{1}{\alpha^n}$ will grow really large

What about $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor +1)^{2}-k $? I suppose it contradicts if the fractional part of $\alpha^n +\frac{1}{\alpha^n}$ can be arbitrarily close to 0 for any irrational but I don't know how to prove it=(

zhihanpeng2.0 wrote: What about $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor +1)^{2}-k $? I suppose it contradicts if the fractional part of $\alpha^n +\frac{1}{\alpha^n}$ can be arbitrarily close to 0 for any irrational but I don't know how to prove it=( Ya i realized that i made this mistake

Though like now if i get done with this one case i am good

zhihanpeng2.0 wrote: What about $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor +1)^{2}-k $? I suppose it contradicts if the fractional part of $\alpha^n +\frac{1}{\alpha^n}$ can be arbitrarily close to 0 for any irrational but I don't know how to prove it=( I guess we can prove it like this i didnt complete it yet $\lfloor \alpha^{2n} \rfloor = (\lfloor \alpha^n +\frac{1}{\alpha^n} \rfloor +1)^{2}-k $ Again then we have $\lfloor \alpha^{n}+\frac{1}{\alpha^n} \rfloor = \lfloor \alpha^{n} \rfloor$ So $\lfloor \alpha^{2n} \rfloor= (\lfloor \alpha^{n} \rfloor+1)^2-k$ define a sequence $b_i=1-\{\alpha^{2^{i-1}n}\}$ and $c_i=\lfloor \alpha^{2^{i-1} n} \rfloor$ for some fixed large $n$. The idea is to show $b_i$ is not bounded above. First we have $c_{i+1}=(c_{i}+1)^2-k$ and $b_{i+1}=c_{i+1}-\alpha^{2^{i-1}n}+1$ Edit : Ok it works !

idkk wrote: Again then we have $\lfloor \alpha^{n}+\frac{1}{\alpha^n} \rfloor = \lfloor \alpha^{n} \rfloor$ Why?

zhihanpeng2.0 wrote: idkk wrote: Again then we have $\lfloor \alpha^{n}+\frac{1}{\alpha^n} \rfloor = \lfloor \alpha^{n} \rfloor$ Why? coz $\lfloor \alpha^{2n} \rfloor \leq ((\lfloor \alpha^{n} \rfloor +1))^2$ [now eventually we will not have any numbers of form $t^2-k$ in the list $((\lfloor \alpha^{n} \rfloor +1))^2,(\lfloor \alpha^{n} \rfloor +1))^2-1,....,(\lfloor \alpha^{n} \rfloor +1)^2-(k-1)$ So as $\lfloor \alpha^{n}+\frac{1}{\alpha^n} \rfloor \geq \lfloor \alpha^{n} \rfloor$ So u can see the onylv value it can take

idkk wrote: $b_{i+1}=c_{i+1}-\alpha^{2^{i-1}n}+1$ Why? And why does this work can you explain in detail plzzz

zhihanpeng2.0 wrote: idkk wrote: $b_{i+1}=c_{i+1}-\alpha^{2^{i-1}n}+1$ Why? And why does this work can you explain in detail plzzz After defining our sequence we prove that it $b_i$ cannot be bounded in $[0,1]$. First observe its much easier to work with $d_i=c_i+1$. we have $d_{i+1}=d_i^2-(k-1)$ we prove $d_i-\alpha^{2^{i-1}n}$ cannot be bounded in the interval. This is a standard reccurence the solving method is pretty straightforward say $d_1=t+\frac{(k-1)}{2t}$ Now we divide into [yet into another casing]. Case 1: $k \geq 3$ Observe $d_{i+1} \geq t^{2^i}+\frac{1}{t^{2^i}}$[this is not hard to prove it i leave it as an excercise to the reader]. So $d_{i+1}-\alpha^{2^{i}} \geq t^{2^i}-\alpha^{2^{i}n}$ Now for large enough $n$ u can easily prove $t > \alpha^{n}$ . [if it dosent u estbalish a upper bound rather] .Hence removing this case as the lower bound can become really large. With some more work u can remove the remaining two cases. Edit: ig i messed up in the $t> \alpha^{n}$ thing