Question : Is the following conjecture true?

Conjecture : Letting $ g_{n,k}(x) = \left\lfloor{\,\sqrt[n]{\,x\,}\,{\left\lfloor{ \,\sqrt[n]{\,x\,}\,\left\lfloor\cdots\left\lfloor \,\sqrt[n]{\,x\,}\,\right\rfloor\cdots\right\rfloor}\right\rfloor}}\right\rfloor $ with $k$ $\,\sqrt[n]{\,x\,}\,$'s, an equation \begin{align} g_{n,n}(x) + \sum_{i = 1}^{n - 1}2^{i - 1}g_{n,n - i}\left(x\right) + 2^{n - 1} - 1 = x\qquad(\star)\end{align}

holds if and only if $x=l^n-1\ (l\ge 2\in\mathbb N)$.

Here, $\left\lfloor\,x\,\right\rfloor$ is the largest integer not greater than $x$.

Example : The $n=4$ case of $(\star)$ is the following :

The conjecture above states that the following equation holds if and only if $x=l^4-1\ (l\ge 2\in\mathbb N)$ such as $x=15, 80, 255, 624,\cdots$. $$\lfloor\sqrt[4]{x}\lfloor\sqrt[4]{x}\lfloor\sqrt[4]{x}\lfloor\sqrt[4]{x}\rfloor\rfloor\rfloor\rfloor+\lfloor\sqrt[4]{x}\lfloor\sqrt[4]{x}\lfloor\sqrt[4]{x}\rfloor\rfloor\rfloor+2\lfloor\sqrt[4]{x}\lfloor\sqrt[4]{x}\rfloor\rfloor+4\lfloor\sqrt[4]{x}\rfloor+7=x.$$

Motivation : I've known the following question :

"Find every $x\gt0\in\mathbb R$ such that $\lfloor\sqrt{x}\lfloor\sqrt{x}\rfloor\rfloor+\lfloor\sqrt{x}\rfloor+1=x$."

The answer is $x=(n+1)^2-1\ (n\in\mathbb N)$. This is in the form of $A^2-1$. Then, I got interested in finding a similar equation whose solutions are in the form of $A^n-1$. This conjecture is true for $n\le 6, x\le 100000$ by using computer. However, I don't have any good idea for proving this conjecture. Can anyone help?


I have what might be a first step towards a solution. Throughout, I assume $n\ge2$ and $x\ge2$.

First, let $$ G_n(x)=g_{n,n}(x)+g_{n,n-1}(x)+2g_{n,n-2}(x)+\cdots+2^{n-1}g_{n,0}(x) $$ where $g_{n,0}(x)=1$. So, we wish to solve $G_n(x)=x+1$.

If $x=l^n$, we get $g_{n,k}(l^n)=l^k$, and so $G_n(l^n)=l^n+(l^n-2)/(l-2)>l^n+1$, which rules out that case.

Assume $l-1<u=\sqrt[n]{x}<l$ for some integer $l$. We write $g_{n,1}(x)=u-\epsilon_1$, and then by induction get the expression $$ g_{n,k}(x)=\lfloor u\cdot g_{n,k-1}(x)\rfloor =u^k-u^{k-1}\epsilon_1-\cdots-u\epsilon_{k-1}-\epsilon_k $$ where $\epsilon_k\in[0,1)$ for $k=1,\ldots,n$. These, we plug into the expression for $G_n(x)$, use $\delta_k=1-\epsilon_k>0$ for simplification, and obtain $$ G_n(x)=u^n+u^{n-1}\delta_1+u^{n-2}(\delta_1+\delta_2)+\cdots +(2^{n-2}\delta_1+\cdots+\delta_{n-1}+\delta_n) $$ where we immediately see that $G_n(x)>x$, hence, $G_n(x)\ge x+1$.

In order to have $G_n(x)=x+1$, the $\delta_k$ need to be strongly bounded. However, I haven't quite figured out how to use this to limit $x$ to $x=l^n-1$.

In particular, $\delta_1<1/u^{n-1}$ is required, which implies that $l=u+\delta_1$ is an integer with $l<u(1+1/x)$. This gives $$ l^n<u^n\left(1+\frac{1}{x}\right)^n<x+n $$ which at least ensures $l^n-n<x<l^n$. I suspect better use of the bounds on the $\delta_k$ may help, but would like to see a less technical proof.

If we plug in $x=l^n-1$, we get $u\approx l-l/nx$. This should be enough to ensure $\delta_k\approx u^k/nx$ which I think should be sufficient to ensure $G_n(x)=u^n+1=x+1$ if $u>2$. However, I haven't had the time to go into the details of this.

I think I see how the rest goes, although what I provide here might not be very complete.

So, let's $\delta=\delta_1=l-u<1/u^{n-1}$, so we have $u=\sqrt[n]{x}=l-\delta$. Let $g_k=g_{n,k}(x)$, so we have $g_1=l-1$. Now, we prove by induction that $g_k=l^k-l^{k-1}-\ldots-l-1$. Assuming this for $g_{k-1}$ and using $g_k=ug_{k-1}-1+\delta_k$, we have $$ g_k=(l-\delta)g_{k-1}-1+\delta_k =(l^k-l^{k-1}-\ldots-l-1)-\delta g_{k-1}+\delta_k $$ where $\delta_k=\delta g_{k-1}<\delta u^{k-1}<1$, giving the desired expression for $g_k$. Note how $\delta u^{n-1}<1$ is required to make this work.

Now that $g_k=l^k-l^{k-1}-\ldots-1$, plugging these into the expression for $G_n$, we get $G_n=l^n$. To show this, we use induction to obtain $g_k+2g_{k-1}+\cdots+2^kg_0=l^k+\cdots+1$: it holds for $g_0=1$, and if it holds for $k-1$ we get $$ g_k+2g_{k-1}+\cdots+2^kg_0=g_k+2\cdot(l^{k-1}+\cdots+1)=l^k+\cdots+1. $$ This makes $G_n=g_n+(g_{n-1}+2g_{n-2}+\cdots+2^{n-1}g_0)=l^n$. Thus, having $G_n=x+1$ requires $x=l^n-1$; the converse should also follow.

  • $\begingroup$ In your answer, there are several points that I can't follow. At least, how can you lead $G_n=l^n$ by plugging $g_k=l^k-l^{k-1}-\cdots -1\ (1\le k\le n)$ into the expression for $G_n$? $\endgroup$ – mathlove Dec 15 '13 at 6:55
  • $\begingroup$ @mathlove: E.g. if you look at the number of $l^k$ in the sum of $G_n$, you get from $g_n,\ldots,g_k$ the coefficients $-1,-1,-2,\ldots,-2^{n-k-2},2^{n-k-1}$, which sums to zero for $k<n$. I'll try to write that part out a little. $\endgroup$ – Einar Rødland Dec 15 '13 at 10:00
  • $\begingroup$ Fine. You use some words such as "might" "should". Could you please explain the following two points? 1)what you could prove. 2)what you can't prove (in other words, what remains unsolved). To be honest, I feel difficulty to read your answer. $\endgroup$ – mathlove Dec 15 '13 at 10:38
  • $\begingroup$ @mathlove: I think, with the addition of the second part, it should be proven that $x$ has to be on the form $l^n-1$. I think the converse, i.e. that $x=l^n-1$ is a solution, follows if you plug in $x=l^n-1$, although I haven't written that part out. At first, I had only a partial proof (up until the line), and I haven't had the time to review and rewrite it to make it more streamlined. $\endgroup$ – Einar Rødland Dec 15 '13 at 11:13
  • $\begingroup$ Thanks. OK, so I need to read your answer again. By the way, you may think the converse would be easy, but it does not seem very easy for me. Do you have an idea? $\endgroup$ – mathlove Dec 15 '13 at 11:42

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.