Can we show algebraically that this is true?

Question

This problem is part of a larger proof I've been working on. Long story short, I'm trying to prove a particular explicit formula for the recursive function

$$ t(p, 0) = 0 \\ t(p, k+1) = \left\lfloor \dfrac{t(p, k)}{3} \right\rfloor + p $$

where $p=2n+1, n \in \mathbb{N}$. The inductive step of proving my particular explicit formula includes the following question:

Can we show algebraically that

$$ \left\lfloor \dfrac{1}{3} - \dfrac{1}{3} \left\lfloor \dfrac{2n-1}{2(3^{k-1})} + \dfrac{1}{2} \right\rfloor \right\rfloor \ \ = \ \ (-1) \left\lfloor \dfrac{2n-1}{2(3^k)} + \dfrac{1}{2} \right\rfloor$$

is true for all $k,n = 1, 2, 3, ...$ ? I used Python to test it and it seems to be true, at least for all $k≤1000, \ n≤1000$. Can anyone prove this rigorously? I tried using induction on $k$ but was not successful. I did not try induction on $n$.

Any help is appreciated.

Answer 1

Claim. Let $m,n$ be integers with $n>0$ and $x$ a real number. Then $$\Bigl\lfloor \frac{-\lfloor x \rfloor+m}{n} \Bigr\rfloor = -\Bigl\lfloor \frac{x-m+n-1}{n} \Bigr\rfloor.$$

Proof. We have \begin{align} \Bigl\lfloor \frac{-\lfloor x \rfloor+m}{n} \Bigr\rfloor &=\Bigl\lceil \frac{-\lfloor x \rfloor+m-n+1}{n} \Bigr\rceil\tag{1}\\ &=-\Bigl\lfloor \frac{\lfloor x \rfloor-m+n-1}{n} \Bigr\rfloor\tag{2}\\ &=-\Bigl\lfloor \frac{\lfloor x-m+n-1 \rfloor}{n} \Bigr\rfloor\tag{3}\\ &=-\Bigl\lfloor \frac{ x-m+n-1 }{n} \Bigr\rfloor\tag{4} \end{align} where we used well-known identities:

1. $\left \lfloor \frac{n}{m} \right \rfloor = \left \lceil \frac{n-m+1}{m} \right \rceil$
2. $\lfloor -x \rfloor=-\lceil x \rceil$ (see Proving that the $\lfloor-x\rfloor= -\lceil x\rceil$)
3. $\lfloor x+m \rfloor=\lfloor x \rfloor +m$ (see Find the value of $\lfloor x+y \rfloor$ where $x \in \mathbb{R}$, $y \in \mathbb{Z}$)
4. $\lfloor \frac{\lfloor x \rfloor}{n} \rfloor = \lfloor \frac{x}{n}\rfloor$ (see How to prove or disprove $\forall x\in\Bbb{R}, \forall n\in\Bbb{N},n\gt 0\implies \lfloor\frac{\lfloor x\rfloor}{n}\rfloor=\lfloor\frac{x}{n}\rfloor$.)

$\square$

Set $m=1,n=3,x=\dfrac{2n-1}{2(3^{k-1})} + \dfrac{1}{2}$ to get your result.

Note. Adding the ceiling version of the claim as an exercise and to make search engines happy (same $m,n,x$ restrictions): $$ \Bigl\lceil \frac{-\lceil x \rceil+m}{n} \Bigr\rceil = -\Bigl\lceil \frac{x-m-n+1}{n} \Bigr\rceil. $$

Answer 2

Let $q = \dfrac{2n-1}{2\cdot 3^k}$, and so $\dfrac{2n-1}{2\cdot 3^{k-1}} = 3q$. Both $q$ and $3q$ are is always positive and never an integer for $k,n = 1,2,3, \ldots$.

Converting the RHS into an inequality,

$$\begin{array}{rcl} \left(q+\dfrac12\right) -1 <& \left\lfloor q+\dfrac12\right\rfloor &\le q+\dfrac12\\ -q+\dfrac12 >& -\left\lfloor q+\dfrac12\right\rfloor &\ge -q-\dfrac12 \end{array}$$

There is exactly one integer in this range.

From the LHS, consider the content inside the outer $\lfloor \ \rfloor$,

$$\begin{align*} \frac13 - \frac13\left\lfloor 3q+\frac12\right\rfloor &= -\frac13\left\lfloor-1+3q+\frac12\right\rfloor\\ &= -\frac13\left\lfloor3q-\frac12\right\rfloor \end{align*}\\ \begin{array}{rcl} \left(3q-\dfrac12\right)-1<& \left\lfloor3q-\dfrac12\right\rfloor &\le 3q-\dfrac12\\ -q+\dfrac12>& -\dfrac13\left\lfloor3q-\dfrac12\right\rfloor &\ge -q+\dfrac16\\ \end{array}$$

The middle $-\frac13\left\lfloor3q-\frac12\right\rfloor$ is a third of an integer. That means its floor satisfy a tighter inequality:

$$\begin{array}{rcl} \left(-\dfrac13\left\lfloor3q-\dfrac12\right\rfloor\right) -\dfrac23 \le& \left\lfloor-\dfrac13\left\lfloor3q-\dfrac12\right\rfloor\right\rfloor &\le -\dfrac13\left\lfloor3q-\dfrac12\right\rfloor\\ \left(-q+\dfrac16\right) -\dfrac23 \le& \left\lfloor-\dfrac13\left\lfloor3q-\dfrac12\right\rfloor\right\rfloor &< -q+\dfrac12\\ -q -\dfrac12 \le& \left\lfloor-\dfrac13\left\lfloor3q-\dfrac12\right\rfloor\right\rfloor &< -q+\dfrac12\\ \end{array}$$

There is also exactly one integer in this range, and this matches the range of the RHS. So

$$LHS = \left\lfloor\frac13 - \frac13\left\lfloor \dfrac{2n-1}{2\cdot 3^{k-1}}+\frac12\right\rfloor\right\rfloor = -\left\lfloor \dfrac{2n-1}{2\cdot 3^k}+\frac12\right\rfloor = RHS.$$