Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps
Here is a rough sketch of how you can solve the second part.
Suppose that the number $n$ is of the form $2^k - 1$ for some non-negative integer $k$ and that the head of the Turing Machine is initially located at the end of the binary representation of $n$ (i.e., at the position of the rightmost, least significant, bit).
Proceed as follows:

While the current tape symbol is a $0$, replace it with $1$ and move the head to the left.
If the current symbol is $1$:

Replace the current symbol with a $0$
Move right until you reach the last non-blank symbol of the tape
Repeat from the beginning


Halt

In analyzing the time complexity, I will ignore the transitions that move right. This is because each of these transitions can be &quot;charged&quot; to a distinct transition that moved the head to the left, and we can safely ignore multiplicative constants in our asymptotic upper bound on the running time.
Notice how, once we ignore these transitions, at most a constant number of steps pass from the instant in which a TM flips a bit of the input tape, to the instant when the next bit flip happens. Then, to estimate the running time we can just count the overall number of bit flips.
Consider all values of $n$ from $2^k-1$ down to $0$, in this order.
The rightmost bit changes every time we move from one value to the next.
The 2nd to last bit changes every other time, the 3rd to last bit changes once every $4$ values, and so on.
In general, the $i$-th least significant bit changes once every $2^{i-1}$ values.
The total number of bit flips is then:
$$
n + \frac{n}{2} + \frac{n}{4} + \dots  = O\left(\sum_{i=0}^\infty \frac{2^k}{2^i}\right) = O(2^k) = O(n)
$$