For each positive real number $r$, define $a_0(r) = 1$ and $a_{n+1}(r) = \lfloor ra_n(r) \rfloor$ for all integers $n \ge 0$. (a) Prove that for each positive real number $r$, the limit \[ L(r) = \lim_{n \to \infty} \frac{a_n(r)}{r^n} \]exists. (b) Determine all possible values of $L(r)$ as $r$ varies over the set of positive real numbers. Here $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.
Problem
Source: 2021 Simon Marais, A4
Tags: calculus, real analysis
PhiloMath_2001
04.11.2021 09:08
Though I would love to see a rigorous solution, my guess is that $$L(r)=\begin{dcases} 0 & 0<r<1 \\ 1 & r\ge 1 \\ \end{dcases}$$. The case for $r\in [0,1) $ is straightforward note that if $r\in [0,1) \implies a_{n}(r)=0 \forall n\in\mathbb{N}-\{0\}$. for the other one I have a very vague way of doing it, you could see that $a_{n}(r)=O(\lfloor r\rfloor^n)$ then the limit follows. $\textbf{Note}$: Actually once you have done the second part first, we can just you the limit definition to show that there are actually limits for $L(r)$ and then the ones we have found are those limits (Uniqueness of Limits).
I3628800
04.11.2021 10:27
@above, $r=2.5$ would give the counterexample. The limit is greater than 0 nevertheless smaller than 1(since the ratio goes to 1 from downside). Here's the proof for (a): Let $\frac{a_{n}}{r^{n}}=b_{n}$. The recurrence relation becomes $b_{n+1}=\frac{[r^{n+1}b_{n}]}{r^{n+1}}\leq b_{n}$. Since the sequence $b_{n}$ is bounded below($\geq 0$) and non-increasing, it converges to a certain limit (by MCT) which actually happens to be $L(r)$. Guess for (b): $0$ or $(0.5, 1]$ with educated(??) trial. $0$ comes from $1.1$ and $1$ comes from $1$, ...
Moubinool
04.11.2021 10:53
Interesting
PhiloMath_2001
07.11.2021 10:51
Anyone has the proof for part b)??
Saucitom
08.11.2021 14:59
(a) For $r>0$, define $L_{n}(r)$ as: $$ L_{n}(r) = \frac{a_{n}(r)}{r^{n}} $$As it was shown before, $(L_{n}(r))_{n \geq 1}$ is decreasing, bounded below by $0$, hence convergent to a limit $L(r)$. (b) We will prove the following result: $$ L(]0,+\infty[) = \left]\frac{1}{2}, 1\right] \cup \{0\} $$ To achieve this, we need some preliminary results on $L(r)$. Result 1: For all $r>0$, $L(r)\leq L(r+1)$
First, we will prove by induction that:
$$
a_{n}(r+1) \geq \sum_{k=0}^{n}\binom{n}{k}a_{k}(r)
$$The statement is obviously true for $n=0$. Now, in the general case, the induction hypothesis implies:
$$
\begin{aligned}
a_{n}(r+1)&=\lfloor (1+r)a_{n-1}(r+1) \rfloor\\
&=a_{n-1}(r)+\lfloor r a_{n-1}(r+1)\rfloor\\
&\geq \sum_{k=0}^{n-1}\binom{n-1}{k}a_{k}(r)+\left\lfloor \sum_{k=0}^{n-1}\binom{n-1}{k} r a_{k}(r)\right\rfloor\\
\end{aligned}
$$But, $r a_{k}(r) \geq a_{k+1}(r)$, hence:
$$
\begin{aligned}
a_{n}(r+1)&\geq \sum_{k=0}^{n-1}\binom{n-1}{k}a_{k}(r)+\left \lfloor \sum_{k=1}^{n} \binom{n-1}{k-1}a_{k}(r)\right \rfloor
&= \sum_{k=0}^{n-1}\binom{n-1}{k}a_{k}(r)+\sum_{k=1}^{n} \binom{n-1}{k-1}a_{k}(r)\\
&=\sum_{k=0}^{n}\binom{n}{k}a_{k}(r)
\end{aligned}
$$which concludes the induction.
Finally, using this preceding result and the fact that $r^{n} a_{k}(r) \geq r^{k} a_{n}(r)$ for $0 \leq k \leq n$, we have:
$$
\begin{aligned}
L_{n}(r+1)-L_{n}(r)&=\frac{1}{r^{n}(r+1)^{n}}(r^{n}a_{n}(r+1)-(r+1)^{n} a_{n}(r))\\
&\geq \frac{1}{r^{n}(r+1)^{n}} \sum_{k=0}^{n} \binom{n}{k}\left(r^{n}a_{k}(r)-a_{n}(r)r^{k}\right)\\
&\geq 0
\end{aligned}
$$Hence, $L(r+1) \geq L(r)$.
Result 2: $L_{n}$ converges uniformly to $L$ which is right continous.
Let's distinguish two cases:
- If $r<2$, then for all $n \geq 1$, $L_{n}(r)=L(r)=0$.
- If $r\geq 2$, we have:
$$
\begin{aligned}
L_{n}(r)-L_{n+1}(r) &= \frac{\{r a_{n}(r)\}}{r^{n+1}}\\
&\leq \frac{1}{2^{n+1}}
\end{aligned}
$$Hence, combining the two preceding results, we have:
$$
\sup_{r >0} |L_{n}(r)-L(r)| \leq \frac{1}{2^{n}}
$$The uniform convergence is proved.
Now, the right continuity of $L$ is a consequence of the right continuity of each $a_{n}$ which can be proved by induction.
More precisely, if $a_{n-1}$ is right continous, then it is easily verified that $r >0 \longrightarrow ra_{n}(r)$ is right continous, increasing. Now, the right continuity is preserved when composing with $\lfloor . \rfloor$, so $a_{n}$ is right continous.
As each $L_{n}$ is right continous and $(L_{n})_{n \geq 1}$ converges uniformly to $L$, $L$ is right continous.
Remark: The functions $a_{n}$ are not right only continuous, but also piecewise constant. This fact will be useful later and can be proved by induction.
Result 3 (Intermediate value theorem): For $r \in [2,+\infty[$ and $n \geq 0$, let $I_{n}(r)=L_{n}([2,r[)$ and $I_{n}=L_{n}([2,+\infty[)$. Then: - $I_{n}(r)$ is connected. - $(I_{n})_{n \geq 1}$ is increasing and: $$ I := \bigcup_{n \geq 1}I_{n} = \left] \inf_{r\geq 2} L(r),1\right] $$
The proof consist in showing that $I_{n}(r)=]i_{n}(r),1]$ where $i_{n}(r)=\inf_{s \in [2,r[} L_{n}(s)$. I won't make any detailed proof (it is quite tedious) but I will give the main idea.
Each $a_{n}$ is a piecewise constant function and at each discontinuities, $a_{n}$ increases by $1$. Let $\mathcal{D}_{n} = \{r_{i}\}_{i \geq 1}$ be the points of discontinuity of $a_{n}$ on $[2,+\infty[$ with the convention that $r_{i} < r_{i+1}$ and define $r_{0}=2$.
On $[r_{i},r_{i+1}[$, $a_{n}$ is constant, hence $L_{n}$ is decreasing.
At a point of discontinuity, $a_{n}$ increases, hence $L_{n}(r_{i})>L_{n}(r_{i}^{-})$ where $L_{n}(r_{i}^{-})$ denotes the left limit of $L_{n}$ at $r_{i}$. On the other hand, $L_{n}(r_{i})\leq 1$.
If you combine these two preceding facts, it is quite clear why the statement should hold (make a picture to convince yourself).
$I_{n}$ is now connected as an increasing union of connected sets and $I_{n} \subset [0,1]$ as $0 \leq L_{n} \leq 1$.
Moreover, we can check that:
$$
I_{n}=\left]\inf_{r \geq 2}L_{n}(r),1\right]
$$Finally, $L_{n} \geq L_{n+1}$, so $I_{n} \subset I_{n+1}$ and:
$$
\begin{aligned}
I &= \bigcup_{n \geq 1} \left]\inf_{r \geq 2}L_{n}(r),1\right]\\
&=\left]\lim_{n \to +\infty} \inf_{r \geq 2}L_{n}(r),1\right]\\
&=\left]\inf_{r \geq 2} L(r), 1\right]
\end{aligned}
$$the last equality being a consequence of the uniform convergence of $L_{n}$ to $L$.
Result 4: $\inf_{r \geq 2}L(r)=\frac{1}{2}$
With result 1, we have:
$$
\inf_{r\geq 2}L(r) = \inf_{2 \leq r<3}L(r)
$$
Now, for $r \in [2,3[$:
$$
\begin{aligned}
\frac{2}{r}-L(r)&=L_{1}(r)-L(r)\\
& = \sum_{n=1}^{+\infty}L_{n}(r)-L_{n+1}(r)\\
&\leq \sum_{n=2}^{+\infty}\frac{1}{r^{n}}\\
&=\frac{1}{r}\frac{1}{r-1}
\end{aligned}
$$Rearranging the inequality, we have:
$$
L(r) \geq \frac{2}{r}-\frac{1}{r}\frac{1}{r-1}
$$
Hence:
$$
\inf_{r \geq 2} L(r) \geq \inf_{2 \leq r < 3} \left(\frac{2}{r}-\frac{1}{r(r-1)}\right)= \frac{1}{2}
$$
On the other hand, fix $n>1$. As $L_{n}(r)$ decreases to $L(r)$ we have:
$$
\begin{aligned}
\inf_{r \geq 2}L(r) &\leq \lim_{n \to +\infty} \inf_{2 \leq r <3} L_{n}(r)\\
&\leq \lim_{n \to +\infty} \lim_{r \to 3^{-}} \frac{a_{n}(r)}{r^{n}}
\end{aligned}
$$But $a_{n}(r)=\frac{1}{2}(3^{n}+1)$ in a left neighborhood of $3$, a fact that can easily be checked by induction.
Hence:
$$
\begin{aligned}
\inf_{r \geq 2}L(r) &\leq \lim_{n \to +\infty}\frac{3^{n}+1}{23^{n}}\\
&=\frac{1}{2}
\end{aligned}
$$
Consequence: $L([2,+\infty[) = \left]\frac{1}{2},1\right]$
Combining results 2, 3 and 4, we have:
$$
L([2,+\infty[) \subset \left[\frac{1}{2},1\right]
$$Now, select $y \in \left]\frac{1}{2},1\right]$ and let $r_{n}=\inf \{2 \leq r < 3 \, : \, L_{n}(r_{n})=y\}$. Result 3 implies that $r_{n}$ isdefined at least for $n$ large enough. We will now prove that the sequence $(r_{n})$ is decreasing. Indeed:
$$
L_{n+1}(r_{n}) \leq L_{n}(r_{n})=y
$$Now, as $L_{n+1}(2)=1$, the Intermediate value theorem (result 3) implies that $r_{n+1}\leq r_{n}$.
Let $r$ be the limit of $(r_{n})$. As $L$ is right continous and $(L_{n})$ converges uniformly to $L$, we have:
$$
\begin{aligned}
L(r)&=\lim_{n \to +\infty}L(r_{n})\\
&=\lim_{n \to +\infty} L_{n}(r_{n})\\
&=y
\end{aligned}
$$We have proved so far that:
$$
\left]\frac{1}{2},1\right] \subset L([2,+\infty[) \subset \left[\frac{1}{2},1\right]
$$It remains to prove that $\frac{1}{2}$ is never reached by $L$. This follows from the inequality (which proved before):
$$
L(r) \geq \frac{2}{r}-\frac{1}{r(r-1)}>\frac{1}{2}
$$for $2 < r <3$ and the fact that $L(2)=1$.
As $L(r)=0$ if $r<2$, we can now conclude that: $$ L(]0,+\infty[)=\{0\} \cup \left]\frac{1}{2},1\right] $$ Edit: you can find in the attachement a graph of $L_{15}(r)$ on $[2,3[$, which shoud be quite close to the graph of $L(r)$.
Attachments:
oty
10.11.2021 23:59
@Saucitom you are officialy top 3 of the best problem solver in our forum for me. Thank you for your contribution.