CN-SMO 2020 Problem 8

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)$ .