If $k$ is the smallest integer such that $[a^k]>[a]^k$, which of the following is true?

Question

This is a question from the KVPY(SX)-2014 (an examination to get into various research institutes in India) paper.

Q. For a real number $r$ let $[r]$ denote the largest integer less than or equal to $r$. Let $a > 1$ be a real number which is not an integer and let $k$ be the smallest positive integer such that $[a^k] > [a]^k$. Then which of the following statements is always true?

$(A)\,\, k\le 2([a]+1)^2\quad (B) \,\, k\le ([a]+1)^4\quad (C)\,\, k\le 2^{[a]+1}\quad (D)\,\, k\le\frac{1}{a-[a]}+1$

The solutions which I’ve looked through on the Internet and on the booklet I’ve been given mostly state that by taking different values of a and k, option B is possible ( e.g. here). But have not provided a proof on why. Or have put forward a proof that doesn't click my head (e.g. this).

I'm looking for a proof that suits the needs for a 12th grader in India.

Answer 1

Update: Note the answer below is for the earlier version of the post's question, i.e., $[ak] \gt [a]k$. As requested by the OP, and I agree, I'm leaving it here for anybody who's interested.

Let

$$a = n + r, \; n \in \mathbb{N}, \; n \ge 1, \; r \in \mathbb{R}, \; 0 \lt r \lt 1 \tag{1}\label{eq1A}$$

Note $0 \lt r$ since it's stated $a$ is not an integer. Thus,

$$\lfloor a \rfloor = n, \; r = a - \lfloor a \rfloor \tag{2}\label{eq2A}$$

Have $k$ be a positive integer where

$$\begin{equation}\begin{aligned} \lfloor ak \rfloor & \gt \lfloor a \rfloor k \\ \lfloor (n+r)k \rfloor & \gt nk \\ \lfloor nk + rk \rfloor & \gt nk \\ nk + \lfloor rk \rfloor & \gt nk \\ \lfloor rk \rfloor & \gt 0 \\ rk & \ge 1 \\ (a - \lfloor a \rfloor)k & \ge 1 \\ k & \ge \frac{1}{a - \lfloor a \rfloor} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

The smallest $k$ would be the ceiling function (i.e., $\lceil \; \rceil$, which designates the smallest integer greater than or equal to the value) of the right hand side, which would be at most up to just less than $1$ more than the value, i.e.,

$$k = \left\lceil \frac{1}{a - \lfloor a \rfloor} \right\rceil \lt \frac{1}{a - \lfloor a \rfloor} + 1 \tag{4}\label{eq4A}$$

Thus, option (D) is the correct one as always being true, although as shown above you can actually replace the $\le$ with the slightly more strict $\lt$.

Answer 2

You can argue for (D) by ruling out (A), (B), and (C), on the basis that they depend only on $[a]$, and not $[a]-a$. Any bound on $k$ depending only on $[a]$ can be defeated by choosing $a-[a]$ small enough. This kind of reasoning is quick and may be valuable on a timed test.

To see why (D) works (this part is unnecessary to answer the multiple choice question, but is a good sanity check if there is time), write $a = n+r$, where $n\in \mathbb{Z}$ and $0 < r < 1$. Put $k = \lceil 1/r \rceil$. We must show $(n+r)^k - n^k \ge 1$. By the binomial theorem, $$ (n+r)^k - n^k = \sum_{i=1}^k \binom{k}{i} r^i n^{k-i} \ge k r n^{k-1} \ge n^{k-1} \ge 1 $$