The last soldier does not change its position. The rest of the soldiers regroup just as in the case, when the last soldier was not there, and the number of the soldiers was $2^n - 1$. So, it suffices to prove the claim for $2^n - 1$ soldiers. We show that after $n$ rearrangements the soldiers are in positions, which can be found in the original line by counting cyclically every $2^i$-th soldier (after the last soldier we go to the first one). Indeed, after 0 rearrangements, the claim clearly holds, and every rearrangement makes us cyclically count every second soldier in the previous line (after the last soldier we go to the second one), the first soldier will still be counted first. After $n$ rearrangements the soldiers in the new line can be found by counting every $2^n$-th soldier in the old line with $2^n - 1$ soldiers. Since the remainder of $2^n$ when divided by $2^n - 1$ is 1, this is equivalent to simply counting the soldiers. This means that we get back the original line.

Enumerate the soldiers starting from 0, and write the numbers in binary form (adding leading zeros to make the lengths of the binary codes equal; for example for $n = 3$ we have the numbers 000, 001, 010, 011, 100, 101, 110, 111). After a rearrangement the soldiers stand in such a way that when reinterpreting the last digit as the first one (but leaving the order of the rest of the digits the same), the soldiers are again enumerated by consecutive numbers. After $n$ rearrangements the binary code of the soldiers has returned to the original, so every soldier's position corresponds to their original position in the line.