International Mathematical Olympiad 2019 — Official contest Question 5

Let $n$ be a positive integer. Harry has $n$ coins lined up on his desk, which can show either heads or tails. He does the following operation: if there are $k$ coins which show heads and $k \gt 0$, then he flips the $k$th coin over; otherwise he stops the process. (For example, the process starting with $THT$ would be $THT \to HHT \to HTT \to TTT$, which takes three steps.)

Prove the process will always terminate, and determine the average number of steps this takes over all $2^n$ configurations.