Evaluate $\lim_{n\to\infty} \frac{b_n}{n}$ define a sequence $a_n = (1-a_{n-1})(1-a_{[n/2]})$ where $[k]$ represents the largest integer $s\leq k$ and $a_1 = 1$. Furthermore, define $b_n = \sum_{k = 1}^{n} a_k$. Evaluate $$\lim_{n\to\infty} \frac{b_n}{n}.$$
For now I have been able to prove by contradiction that $a_k = 1 \implies k \equiv 0$ (mod 2) and by writing a simple python program I realised the expression seems to tend to $1/3$. How can this result be proven mathematically?
 A: This is not an answer, just notes too long for comments. You have already proved that the odd terms (except from 1) are zero. So, using the recurrence, you can compute the even terms as
$$
a_{2s} = (1-\underbrace{a_{2s-1}}_{=0})(1- a_s) = 1 - a_s
$$
Every even number can be written, in a unique way, in the form $n = 2^k m$, where $m$ is an odd number. Let's look at a few examples:

*

*$10 = 2^1 \times 5$:
$$
a_{10} = a_{2\times 5} = 1-a_5 = 1-0 = 1
$$


*$20 = 2^2\times 5$:
$$
a_{20} = a_{2\times 10} = 1 - a_{10} = 1 -a_{2\times 5} = 1 - (1-a_5) = 0
$$


*$8 = 2^3 \times 1$:
$$
a_{2^3} = 1-a_4 = 1-(1-a_2) = 1-(1-(1-a_1))) = 0
$$


*$16 = 2^4 \times 1$:
$$
a_{16} = 1 - a_8 = 1-0 = 1
$$
So, the power $k$ tells you how many times you flip between 1 and 0.
In general, if $m \ne 1$, $a_{2^k m} = \frac{1 - (-1)^k}{2}$. When $m=1$, $a_{2^k} = \frac{1+(-1)^k}{2}$.
The nonzero terms are exactly the ones for which $ n = 2^{2k-1} m$, with odd $m$.
With these tools we are able to compute $b_n$ for any $n$. If $b_n$ converges, its limit will coincide with the limit of any subsequence. for instance, for $k \ge 2$ you can establish that
$$
b_{2^{2k}} = \frac{1}{2^{2k}}\sum_{n=1}^{2^{2k}} a_n = 
\frac{1}{2^{2k}}(\frac 13 4^{k}+\frac 23)  \to \frac 13  $$
It remains to show that the sequence converges.
A: Observe $a_n$ series peacefully that series look like as shown below:
$10010100010001010100010101000100010001010100010001000101010001010...$
So when we will be solving for limit $n→∞$ it should be equal to $W/n$ where $W$ is the total number of '1' that occurred in the series so our aim is to generate a formula that can help us to find $W$.
We will try different values of n to understand how limit approaches to 1/3 as shown below:
TRIAL 1 $n=10$ then W=4 hence $lim_{n→∞}{{b_n/n}} $ approximate to 4/10
TRIAL 2 $n=100$ then W=34 hence $lim_{n→∞}{{b_n/n}} $ approximate to 34/100
TRIAL 3 $n=1000$ then W=334 hence $lim_{n→∞}{{b_n/n}} $ approximate to 334/1000
TRIAL 4 $n=10000$ then W=3333 hence $lim_{n→∞}{{b_n/n}} $ approximate to 3333/10000
TRIAL 5 $n=100000$ then W=33335 hence $lim_{n→∞}{{b_n/n}} $ approximate to 33335/100000
Ok so now we understood why answer is $0.3333333333333333333333.....$ for n approaching to infinity.
Now assume you have calculated out $f(n)$ which help us to find $W$ so divide it by n to get your answer :).
Try for $f(n)$ if you are not getting I am still here to help in the comment section.
