Convergence of $(u_n)_n$, assuming $u_n+\frac{u_{2n}}{2}$ converges. Following this post on Meta, I am going to regularly ask questions from competitive mathematics exams, on a variety of topics; and provide a solution a few days later. The goal is not only to list interesting (I hope) exercises for the sake of self-study, but also to obtain (again, hopefully) a variety of techniques to solve them.

Let $(u_n)_{n\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$ be a bounded sequence such that $\lim_{n\to\infty} u_n+\frac{u_{2n}}{2}$ exists. (i) Show that $(u_n)_{n\in\mathbb{N}}$ converges. (ii) Does it remain true if $(u_n)_{n\in\mathbb{N}}$ is not assumed bounded?

Reference: Exercise 2.12 in Exercices de mathématiques: oraux X-ENS (Analyse I), by Francinou, Gianella, and Nicolas (2014) ISBN 978-2842252137. (First part of the question only.)
 A: Suppose $\lvert u_n\rvert \leqslant K$ for all $n$.  Let
$$\omega := \limsup_{n\to \infty} u_n - \liminf_{n\to \infty} u_n \geqslant 0.$$
Let $v_n = u_n + \frac{1}{2}u_{2n}$ for $n\in \mathbb{N}$. Part of the assumption is that $v_n$ converges, and hence so does
$$w^{(r)}_n := \sum_{k = 0}^r \frac{(-1)^k}{2^k}v_{2^kn} = u_n + \frac{(-1)^r}{2^{r+1}}u_{2^{r+1}n}$$
for every fixed $r\in \mathbb{N}$. Since
$$0 = \limsup_{n\to\infty} w^{(r)}_n - \liminf_{n\to\infty} w^{(r)}_n \geqslant \limsup_{n\to\infty} u_n - \frac{K}{2^{r+1}} - \liminf_{n\to\infty} u_n - \frac{K}{2^{r+1}} = \omega - \frac{K}{2^r}$$
for every $r$, it follows that $\omega = 0$, i.e. $(u_n)$ converges.
Without the boundedness assumption, let
$$u_{2^k\cdot (2m+1)} = (-2)^k,$$
then we have $u_n + \frac{1}{2}u_{2n} = 0$ for all $n > 0$, but clearly $(u_n)$ isn't convergent.
A: A solution (similar in spirit to that of the book cited in reference, although found before looking at it).
(i) Since the assumption that $(u_n)_n$ be bounded seems to play a major role given the statement, a natural idea is to check what we know about bounded real sequences. Well, two related things:


*

*any bounded real sequence has a convergent subsequence;

*if a bounded real sequence only has one adherence value, then it converges to that value.


So let us prove that $(u_n)_n$ has a unique adherence value (limit point). To do so, first let us denote by $\ell$ the limit guaranteed by assumption, that is 
$$\ell \stackrel{\rm def}{=} \lim_{n\to \infty} u_n + \frac{u_{2n}}{2}\tag{1}.$$
Now, let $\ell_0$ be any limit point of $(u_n)_n$ (by the above bullet points, we know there is at least one), and $\varphi\colon\mathbb{N}\to\mathbb{N}$ be an increasing function define a corresponding subsequence: $$\lim_{n\to \infty} u_{\varphi(n)} = \ell_0.\tag{2}$$
From (1) and (2), we immediately get that
$$
u_{2\varphi(n)} = 2\left(u_{\varphi(n)}+\frac{u_{2\varphi(n)}}{2}\right) - 2u_{\varphi(n)} \xrightarrow[n\to\infty]{} 2\left(\ell-\ell_0\right)
$$
and therefore $\ell_1\stackrel{\rm def}{=} -2\ell_0+2\ell$ is also a limit point of $(u_n)_n$. But we can repeat the above:and the sequence of values $(\ell_k)_{k\geq 0}$ defined by
$$
\ell_{k+1} = -2\ell_k+2\ell \tag{3}
$$
is a sequence of limit points of $(u_n)_n$. Solving the linear recurrence (e.g., writing $\ell_{k+1}-\frac{2}{3}\ell = -2(\ell_k-\frac{2}{3}\ell)$ to get a geometric series), we get $$\ell_k = (-2)^k\left(\ell_0-\frac{2}{3}\ell\right)+\frac{2}{3}\ell\tag{4}$$
for every $k\geq 0$. But this sequence of limit points has to be bounded, since the sequence $(u_n)_n$ is: this is only possible if $\ell_0-\frac{2}{3}\ell=0$.
Therefore, $(u_n)_n$ has a unique adherence value, namely $\frac{2}{3}\ell$ — and thus converges to this value. $\square$

(ii) Now, without the assumption that $(u_n)_n$ be bounded, the argument above breaks in two places: and indeed the counterexample given by Daniel Fischer shows that this is not only an artifact of the proof, but that the conclusion does not hold.
A way to get to such a counterexample would be to start with a natural simplification: let us impose that
$$
u_n + \frac{u_{2n}}{2} \xrightarrow[n\to\infty]{} 0
$$
and even more stringent that $u_n + \frac{u_{2n}}{2} = 0$ for all $n\geq 0$. (Clearly, this implies the limit, and the least freedom we have, the simpler it is to get or fail to get a counterexample).
Reorganizing, we see that this implies $u_{2n} = -2 u_n$ for all $n\geq 0$, which naturally leads to set
$$
u_n \stackrel{\rm def}{=} \begin{cases}
(-2)^k u_0 &\text{ if } n=2^k\text{ for some }k\geq 0\\
0 &\text{ otherwise.}
\end{cases}
$$
