Linear recurrence relation in Cantor-like sets I have a linear recurrence relation 
$$a_i = \alpha_0 a_{i-1} + \beta(i)$$
Where $\beta(i) = \beta_0b_i$ with $b_i \in \{0,1\}^\mathbb N$
I know that $0 < \alpha_0 < \frac{1}{2}$, $\beta_0 = 1 - \alpha_0$ and $a_1 \in [0,1]$
How can I express $\lim_{i \to \infty}a_i$ in terms of $b_i$?
The best I can get currently seems to be $\lim_{n \to \infty} \sum_{i=0}^{n-2} (\alpha_0^{i}-\alpha_0^{i+1})b_{n-i}$
This problem came up when looking at the Middle-m cantor-like sets. These are sets defined by the IFS $\{ S_0,S_1 \}$ with the contractions $S_0(x)=\frac{(m-1)x}{2m}$ and $S_1(x)=\frac{(m-1)x + m + 1}{2m}$
I was pretty sure that 
$$lim_{n \to \infty}S_{b_n}\circ \dotsb \circ S_{b_0}([0,1])$$
should be a point on the set.
 A: Preliminaries
(I didn't have time to write this short, so I wrote it long.) I'll take your recurrence relation to be $$a_{i+1} = \alpha_0 a_{i} + (1-\alpha_0) b_i,\hspace{.5cm} a_1,b_i \in [0,1],$$ The slight shift in indices is just so that $b_1$ plays a role--right now $b_2$ is the first that matters, and I dislike the asymmetry. For the moment, I'll make no assumptions as to the sequence $\{b_i\}$.
To analyze this recurrence, I'll give a demonstration of the generating functions method in analytic combinatorics. We introduce the generating functions $$A(z)=\sum_{i=0}^\infty a_{i+1} z^i,\hspace{1cm} B(z)=\sum_{i=0}^\infty b_{i+1} z^{i}$$ We will consider these as formal power series in $z$; that is, we won't worry about their convergence or evaluation. Observe that we may write 
\begin{align} A(z)
&= a_1+\sum_{i=1}^\infty a_{i+1} z^i \\ 
&= a_1+\sum_{i=1}^\infty \Big[\alpha_0 a_{i} + (1-\alpha_0) b_i\Big]z^{i} \\
&= a_1+\alpha_0 \sum_{i=1}^\infty a_{i}z^{i} 
+ (1-\alpha_0) \sum_{i=1}^\infty b_i z^{i}\\
&=a_1+\alpha_0 z A(z)+(1-\alpha_0)z B(z)
\end{align}
which we may solve for $A(z)$ as
$$A(z)=\frac{a_1+(1-\alpha_0)z B(z)}{1-\alpha_0 z}=\frac{a_1}{1-\alpha_0 z}-  B(z) \left(\frac{1-z}{1-\alpha_0 z}\right)+B(z).$$ What this means is that we can now find the power series for $A(z)$ (and therefore the relevant coefficients) by expanding the RHS. 
Analysis of different $b_i$ sequences
Note, though, one issue: we've made now assumptions as to the behavior of $B(z)$. This is a problem, since the behavior of the high-order coefficients (i.e. $\lim_{n\to\infty} a_n$) depends greatly on the particular sequence of $b_i$. Three cases will demonstrate this point:


*

*Suppose $B(z)=0$ (i.e. all $b_i=0$). Then $A(z)=\dfrac{a_1}{1-\alpha_0 z}$ and therefore its $n$th coefficient is $a_n=[z^n]A(z)=a_1\alpha_0^n$. Hence the coefficients converge geometrically to zero from above.

*Suppose we instead want $b_i=1$ always. Then $B(z)=(1-z)^{-1}$ and therefore  $A(z)=\dfrac{1}{1-z}-\dfrac{1-a_1}{1-\alpha_0 z}$ which gives coefficients 
$a_n=1-(1-a_1)\alpha_0^n$. Hence $a_n$ converges geometrically to 1 from below.

*Suppose $b_i$ flips from 0 to 1 indefinitely. Then $B(z)=(1-z^2)^{-1}$, and a (tedious) partial fractions decomposition gives 
$$A(z)=\frac{1}{1-\alpha_0 z}\left(a_1 -\frac{\alpha_0}{1+\alpha_0}\right)
+\frac{1}{1+\alpha_0}\frac{1}{1+z}+\frac{1}{1-z^2}$$
which finally gives 
$$a_n=\left(a_1 -\frac{\alpha_0}{1+\alpha_0}\right)\alpha_0^n
+\left\{
\begin{array}{cc}
1+\alpha_0^{-1} ,&   n\text{ even}\\ 
1+\alpha_0,& n\text{ odd}
\end{array}\right\}^{-1} $$
The first term displays the familiar geometric convergence to zero. The second term, by contrast, remains finite and is different between even and odd $n$. That means that the even and odd subsequences converge to different values; in other words, as $n\to\infty$ the map converges to the limit 2-cycle $\left\{\dfrac{1}{1+\alpha_0^{-1}},\dfrac{1}{1+\alpha_0}\right\}$ for all $0 <\alpha_0 <\frac12$.
Conclusions
Such analysis may be carried out for other $\{b_i\}$, but one's patience is quickly exhausted. (A wiser approach is to do a singularity analysis of the generating function---see Flajolet & Sedgwick's Analytic Combinatorics for an extensive treatment.) What should be clear from this treatment is that different sequences create vastly different behavior, and one cannot guarantee convergence to a fixed point. 
Which, upon reflection, is not so shocking: The first map sends $a_n\in[0,1]$ to $[0,\alpha_0]\subset[0,1]$; the second, to $[1-\alpha_0,1]$. (Note that these intervals are disjoint when $\alpha_0<\dfrac{1}{2}$.) So if we only do one of the maps, we surely get a fixed point; if we oscillate back and forth, we can only hope for a limit cycle. Higher periodicities presumably lead to limit cycles of greater (even) length. (I suspect that, if one takes $b_i$ to be a random variable, then the resulting behavior will be ergodic on $[0,\alpha_0]\cup[1-\alpha_0,1]$.)
