Closed form for a markov chain, where transition probabilities depend on $n$? Let $A_n$ be an event whose success probability $P(A_n)$ depends on the size, $n\in \mathbb{N}$, of a given sample.
Let $d$ be a fixed positive integer.
For the problem I am working on I can assume a sequential sample and derive  - via a geometric argument - the following recurrence relation:
$$ P(A_{n+1}) = P(A_{n+1}|A_n)P(A_{n}) + P(A_{n+1}|A_{n}^c)P(A_{n}^c)\\
 = P(A_{n}) + 2^{-n}(1 - P(A_{n}))$$
with the initial conditions $P(A_d) =0$, $P(A_{d+1}) = 2^{-d}$.
I am interested in whether it is possible to obtain a simple closed form expression for $P(A_n) = P(A_{d+k})$?
 A: Let $a_{n+1} = \log(1 - \Pr(A_{n+1}))$ for $n=d, d+1, \ldots.$  In these terms the recurrence reads
$$\begin{aligned}
a_{n+1} &= \log(1 - [\Pr(A_n) + 2^{-n}(1 - \Pr(A_n))])\\
&= \log((1-2^{-n})(1 - \Pr(A_n))\\
&= \log(1 - 2^{-n}) + \log(1-\Pr(A_n)) \\
&= \log(1 - 2^{-n}) + a_n
\end{aligned}$$
with initial condition $a_{d+1} = \log(1 - 2^{-d}).$
An easy induction now gives
$$\begin{aligned}
a_{n+d} &= \sum_{i=1}^{n-1} \log\left(1 - 2^{-(d+i)}\right) + a_{d+1}\\
&= \sum_{i=0}^{n-1} \log\left(1 - 2^{-(d+i)}\right).
\end{aligned}$$
Returning to the original formulation,
$$\Pr(A_{n+d}) = 1 - \exp(a_{n+d}) = 1 - \prod_{i=0}^{n-1} \left(1 - q^{-(d+i)}\right)= 1 - \prod_{k=d}^{n+d-1} \left(1 - q^{-k}\right)$$
where $q=1/2.$  Using the conventional notation for q-numbers
$$[k]_q = \frac{1 - q^k}{1-q} = 1 + q + q^2+ \cdots + q^{k-1}$$
we may write this as

$$\Pr(A_{n+d}) = 1 - 2^{-n}\prod_{k=d}^{n+d-1} [k]_{1/2} = 1 - 2^{-n}\binom{n+d-1}{n}_{1/2}\,[n]_{1/2}!$$

where the $q$ analogs to the Binomial coefficients and factorials are the Gaussian Binomial coefficients
$$\binom{m}{r}_q = \frac{[m]_q [m-1]_q \cdots [m-r+1]_q}{[r]_q [r-1]_q \cdots [2]_q [1]_q}$$
and their related factorials
$$[k]_q! = [k]_q [k-1]_q \cdots [2]_q [1]_q.$$
I believe this won't simplify further, but clearly the product converges rapidly and therefore is straightforward to compute and analyze.  In particular, these $q$-numbers have combinatorial interpretations (closely related to sampling without replacement) and enjoy many beautiful mathematical properties that can help with that analysis.
