MathDB

Using a nozzle to paint each square in a

1 \times n

stripe, when the nozzle is aiming at the

i

-th square, the square is painted black, and simultaneously, its left and right neighboring square (if exists) each has an independent probability of

\tfrac{1}{2}

to be painted black.
In the optimal strategy (i.e. achieving least possible number of painting), the expectation of number of painting to paint all the squares black, is

T(n)

. Find the explicit formula of

T(n)

Problem Statement