How would you prove that the sequence $T_n=\left\lfloor \dfrac{T_{n-1}}{3} \right\rfloor + p$ converges after a finite number of iterations?

Question

This problem was posed to me as a dare. I have proven it myself, but I'm curious about what other people come up with, and if someone has a more concise proof than mine. My solution is at the end.

The problem:

Choose some positive odd integer $p$, and some integer $r$ such that $0 ≤ r ≤ 3p-1$. Consider the sequence $(T_n)$ defined recursively by

$$ T_0 = r \\[2ex] T_n = \left\lfloor \dfrac{T_{n-1}}{3} \right\rfloor + p $$

Prove the following:

1. Choose any fixed $p$. Then for all $r$, this sequence always converges to the same value $M$ after a finite number of iterations (although the number of iterations required to converge may be different for different values of $r$).
2. Find the convergence value, $M$, in terms of $p$, i.e. $M = M(p)$.

BONUS POINTS: Find the maximum number of iterations, in terms of $p$, required for the sequence to converge to $M$, no matter what $r$ is.

$$\\$$

---

[Stop reading here if you want to attempt it without seeing my solution.] $$\\$$

Proof:

I will prove that this sequence always converges to $\dfrac{3p-1}{2}$ in a finite number of iterations.

I first prove the case where $p=1$:

Since $0 ≤ r ≤ 3p-1$, we have $0 ≤ r ≤ 2$. Then

$$ T_0 = r \\[2ex] T_1 = \left\lfloor \dfrac{T_0}{3} \right\rfloor + 1 = \left\lfloor \dfrac{r}{3} \right\rfloor + 1 = 1 \\[3ex] T_2 = \left\lfloor \dfrac{T_1}{3} \right\rfloor + 1 = \left\lfloor \dfrac{1}{3} \right\rfloor + 1 = 1 \\ $$

and so on. The sequence doesn't change after reaching $1$, and notice that $\frac{3p-1}{2} = \frac{3(1)-1}{2} = 1$, so the sequence indeed converges to $\frac{3p-1}{2}$ in a finite number of iterations.

For the rest of the proof, $p ≥ 3$.

I first propose the following explicit formulae for $T_n$ when $r=0$ and when $r=3p-1$:

$$ T_n^{(0)} \stackrel{?}{=} \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^{n-1})} + \frac{1}{2} \right\rfloor, \quad r=0 \\[5ex] T_n^{(3p-1)} \stackrel{?}{=} \frac{3p-1}{2} + \left\lfloor \frac{p-2}{2(3^{n-1})} + \frac{1}{2} \right\rfloor, \quad r=3p-1 $$ (I arrived at these formulae empirically, and I will prove them here.)

Notice the new notation I've introduced: $T_n^{(X)}$ means $r=X$ for this sequence. I will now prove these formulae by induction, starting with the first formula where $r=0$:

Claim: $\quad \forall \ n≥1, \ \ T_n^{(0)} = \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^{n-1})} + \frac{1}{2} \right\rfloor$

1. Base case: $n=1$

By definition,

$$ T_1^{(0)} = \left\lfloor \dfrac{T_0^{(0)}}{3} \right\rfloor + p = \left\lfloor \dfrac{0}{3} \right\rfloor + p = p. $$

And evaluating my proposed explicit formula gives us:

$$ \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^{1-1})} + \frac{1}{2} \right\rfloor = \frac{3p-1}{2} - \left\lfloor \frac{p-1}{2} \right\rfloor = \frac{2p}{2} = p $$

because $\frac{p-1}{2}$ is an integer since $p$ is odd. Thus the claim is true for $n=1$.

2. Inductive hypothesis: Assume the claim to be true for some $n=k≥1$.

$$ T_k^{(0)} = \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^{k-1})} + \frac{1}{2} \right\rfloor $$

3. Inductive step: Prove the claim for $n=k+1$.

$$ \begin{align} T_{k+1}^{(0)} &= \left\lfloor \frac{T_{k}^{(0)}}{3} \right\rfloor + p \\[2ex] &= \left\lfloor \frac{\frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^{k-1})} + \frac{1}{2} \right\rfloor}{3} \right\rfloor + p \quad \text{by the inductive hypothesis} \\[2ex] \end{align} $$

For convenience, let's set $x = \frac{p-2}{2(3^{k-1})} + \frac{1}{2}$ and continue:

\begin{align} &= \left\lfloor \frac{\frac{3p-1}{2} - \lfloor x \rfloor}{3} \right\rfloor + p \\[2ex] &= \left\lfloor \frac{\frac{9p-1}{2} - \lfloor x \rfloor}{3} \right\rfloor \\[2ex] &= \left\lceil \frac{\frac{9p-1}{2} - \lfloor x \rfloor -3 +1}{3} \right\rceil \quad \text{by } \left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil \\[2ex] &= \left\lceil \frac{\frac{9p-1}{2} - \lfloor x \rfloor -2}{3} \right\rceil \\[2ex] &= - \left\lfloor \frac{\frac{-9p+1}{2} + \lfloor x \rfloor +2}{3} \right\rfloor \quad \text{by } \lceil -y \rceil = -\lfloor y \rfloor, \ \ y \in \mathbb{R} \\[2ex] &= - \left\lfloor \frac{\left\lfloor \frac{-9p+1}{2} + x +2 \right\rfloor}{3} \right\rfloor \quad \text{since $\frac{-9p+1}{2}$ is an integer} \\[2ex] &= - \left\lfloor \frac{\frac{-9p+1}{2} + x +2}{3} \right\rfloor \quad \text{by } \left\lfloor \frac{\lfloor y \rfloor}{n} \right\rfloor = \left\lfloor \frac{y}{n} \right\rfloor \\[2ex] &= - \left\lfloor \frac{-9p+1}{6} + \frac{x}{3} + \frac{2}{3} \right\rfloor \\[2ex] &= - \left\lfloor \left( \frac{3p-1}{2} - \frac{3p-1}{2} \right) + \frac{-9p+1}{6} + \frac{x}{3} + \frac{2}{3} \right\rfloor \\[2ex] &= \frac{3p-1}{2} - \left\lfloor \frac{3p-1}{2} + \frac{-9p+1}{6} + \frac{x}{3} + \frac{2}{3} \right\rfloor \\[2ex] &= \frac{3p-1}{2} - \left\lfloor \frac{-1}{3} + \frac{x}{3} + \frac{2}{3} \right\rfloor \\[2ex] &= \frac{3p-1}{2} - \left\lfloor \frac{x}{3} + \frac{1}{3} \right\rfloor \\[2ex] \end{align}

Substituting back in $x = \frac{p-2}{2(3^{k-1})} + \frac{1}{2}$:

\begin{align} &= \frac{3p-1}{2} - \left\lfloor \frac{\frac{p-2}{2(3^{k-1})} + \frac{1}{2}}{3} + \frac{1}{3} \right\rfloor \\[2ex] &= \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^k)} + \frac{1}{6} + \frac{1}{3} \right\rfloor \\[2ex] &= \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2 \left( 3^{(k+1)-1} \right)} + \frac{1}{2} \right\rfloor \\[2ex] \end{align}

This final expression is equal to my proposed explicit formula, with $n=k+1$. Thus we have proven by induction that the proposed explicit formula for $T_n^{(0)}$ is correct.

The proof for the proposed explicit formula for $T_n^{(3p-1)}$ is extremely similar to the induction proof above, but simpler. I expect that if the reader can follow the induction proof above, they can trust that the induction proof for $T_n^{(3p-1)}$ would be correct, and thus for convenience I have omitted it here, but know that it's true. Hence we now know two explicit formulae:

$$ T_n^{(0)} = \frac{3p-1}{2} - \left\lfloor \frac{p-2}{2(3^{n-1})} + \frac{1}{2} \right\rfloor \\[5ex] T_n^{(3p-1)} = \frac{3p-1}{2} + \left\lfloor \frac{p-2}{2(3^{n-1})} + \frac{1}{2} \right\rfloor $$

We will now prove that both of these formulae converge to $\frac{3p-1}{2}$ in a finite number of iterations. Consider the floor function term in both formulae:

$$ \left\lfloor \frac{p-2}{2(3^{n-1})} + \frac{1}{2} \right\rfloor $$

One can see that as $n$ grows, eventually the whole expression will evaluate to $0$. This happens when $\frac{p-2}{2(3^{n-1})}$ is less than $\frac{1}{2}$. We can find the point at which this happens:

$$ \frac{p-2}{2(3^{n-1})} < \frac{1}{2} \\[2ex] p-2 < 3^{n-1} \\[2ex] \log_3(p-2) < n-1 \\[2ex] n > 1 + \log_3(p-2) \\[2ex] $$

Clearly $1 + \log_3(p-2)$ is finite for any fixed $p$, so eventually $n$ will exceed this quantity as we iterate. Thus we have:

$$ \forall \ n > 1 + \log_3(p-2), \\[2ex] T_n^{(0)} = T_n^{(3p-1)} = \frac{3p-1}{2} $$

Hence $T_n^{(0)}$ and $T_n^{(3p-1)}$ converge to $\frac{3p-1}{2}$ after a finite number of iterations.

Now we will prove that for all $r$ such that $0 < r < 3p-1$, the sequence $T_n^{(r)}$ is bounded above and below by $T_n^{(3p-1)}$ and $T_n^{(0)}$, respectively. In other words, we want to prove

$$ T_n^{(0)} ≤ T_n^{(r)} ≤ T_n^{(3p-1)}. $$

We will prove this by induction on $n$.

Claim: $\quad \forall \ n≥1, \ \ T_n^{(0)} ≤ T_n^{(r)} ≤ T_n^{(3p-1)} \ \ \text{(for any $0 < r < 3p-1$})$

1. Base case: $n=1$

$$ \begin{align} T_1^{(r)} &= \left\lfloor \frac{T_0^{(r)}}{3} \right\rfloor + p \quad \text{by definition} \\[2ex] &= \left\lfloor \frac{r}{3} \right\rfloor + p \\[2ex] &≥ \left\lfloor \frac{0}{3} \right\rfloor + p \quad \text{since $r>0$} \\[2ex] &= \left\lfloor \frac{T_0^{(0)}}{3} \right\rfloor + p \\[2ex] &= T_1^{(0)} \\[2ex] \end{align} $$

and

$$ \begin{align} T_1^{(r)} &= \left\lfloor \frac{T_0^{(r)}}{3} \right\rfloor + p \quad \text{by definition} \\[2ex] &= \left\lfloor \frac{r}{3} \right\rfloor + p \\[2ex] &≤ \left\lfloor \frac{3p-1}{3} \right\rfloor + p \quad \text{since $r<3p-1$} \\[2ex] &= \left\lfloor \frac{T_0^{(3p-1)}}{3} \right\rfloor + p \\[2ex] &= T_1^{(3p-1)} \\[2ex] \end{align} $$

thus $T_1^{(0)} ≤ T_1^{(r)} ≤ T_1^{(3p-1)}$.

2. Inductive hypothesis: Assume the claim is true for some $n=k≥1$.

$$ T_k^{(0)} ≤ T_k^{(r)} ≤ T_k^{(3p-1)} $$

3. Inductive step: Prove the claim for $n=k+1$.

We have

$$ T_k^{(0)} ≤ T_k^{(r)} ≤ T_k^{(3p-1)} \\[3ex] \frac{T_k^{(0)}}{3} ≤ \frac{T_k^{(r)}}{3} ≤ \frac{T_k^{(3p-1)}}{3} \\[3ex] \left\lfloor \frac{T_k^{(0)}}{3} \right\rfloor ≤ \left\lfloor \frac{T_k^{(r)}}{3} \right\rfloor ≤ \left\lfloor \frac{T_k^{(3p-1)}}{3} \right\rfloor \\[3ex] \left\lfloor \frac{T_k^{(0)}}{3} \right\rfloor + p ≤ \left\lfloor \frac{T_k^{(r)}}{3} \right\rfloor + p ≤ \left\lfloor \frac{T_k^{(3p-1)}}{3} \right\rfloor + p \\[3ex] T_{k+1}^{(0)} ≤ T_{k+1}^{(r)} ≤ T_{k+1}^{(3p-1)} \\[3ex] $$

Therefore the claim is true by induction for all $n≥1$.

$$\\$$

Now, for all $n > 1 + \log_3(p-2)$ we have:

$$ T_n^{(0)} ≤ T_n^{(r)} ≤ T_n^{(3p-1)} \\[2ex] \frac{3p-1}{2} ≤ T_n^{(r)} ≤ \frac{3p-1}{2} \\[2ex] T_n^{(r)} = \frac{3p-1}{2} \\[2ex] $$

Hence $T_n^{(r)}$ converges to $\frac{3p-1}{2}$ after a finite number of iterations for all $0 ≤ r ≤ 3p-1$. Moreover, the maximum number of iterations required for convergence is $n = \lfloor \log_3(p-2) \rfloor + 2$. This concludes the proof.

$\blacksquare$

Answer 1

This more concise solution was formulated by user @Sil.

Proof:

We either have $T_{1} ≥ T_0$ or $T_{1} ≤ T_0$ (or both).

Case 1: Assume $T_{1} ≥ T_0$. Then we can make the inductive hypothesis $T_{k+1} ≥ T_k$ for some $n=k≥0$. Then

$$ T_{k+2} = \left\lfloor \frac{T_{k+1}}{3} \right\rfloor + p ≥ \left\lfloor \frac{T_k}{3} \right\rfloor + p = T_{k+1} $$

Thus by induction $T_{n+1} ≥ T_n$ so the sequence is non-decreasing.

Case 2: Assume $T_{1} ≤ T_0$. We can use the same logic as above to conclude that in this case, the sequence is non-increasing.

Thus the sequence is monotonic.

We can also reason that the sequence is bounded. It's obviously always non-negative so it's bounded below by $0$. And notice that $T_0 = r ≤ 3p-1$ so we can make the inductive hypothesis $T_k ≤ 3p-1$ for some $n=k≥0$. Then

$$ T_{k+1} = \left\lfloor \frac{T_k}{3} \right\rfloor + p ≤ \left\lfloor \frac{3p-1}{3} \right\rfloor + p = 2p-1 ≤ 3p-1 $$

Thus by induction $T_n ≤ 3p-1$ so the sequence is bounded above by $3p-1$. Hence the sequence is bounded.

Side note: Similarly, it's easy to show $T_n ≤ 3p+r$ if we start with $T_0 = r ≤ 3p+r$ for any $r≥0$. However, to be consistent with the premise of the problem, I proved it for only $0≤r≤3p-1$.

Since the sequence is monotonic, bounded, and integer, it must eventually reach a stable value after which each term equals the next. We can find this stable value $M$:

$$ \begin{align} M = \left\lfloor \frac{M}{3} \right\rfloor + p \quad \tag*{since each term equals the next} \\[2ex] \frac{M}{3} + p - 1 < M ≤ \frac{M}{3} + p \\[2ex] M + 3p - 3 < 3M ≤ M + 3p \\[2ex] M-3 < 3M-3p ≤ M \\[2ex] -2M-3 < -3p ≤ -2M \\[2ex] 2M ≤ 3p < 2M+3 \\[2ex] \end{align} $$

And since $3p$ is odd, then it must equal $2M + 1$, hence

$$ 2M+1 = 3p \\[2ex] M = \frac{3p-1}{2} \\[2ex] $$

Thus we have proven that the sequence converges to $\frac{3p-1}{2}$ after a finite number of iterations. This concludes the proof.

$\blacksquare$

---

NOTE: Unlike my original solution posted in the question, this solution doesn't prove that the maximum number of iterations required to converge is $\lfloor \log_3(p-2) \rfloor + 2$. I'm not sure how to succinctly prove this without finding an explicit formula as I did in my original solution. If you figure it out, I'll add it and give you credit.