Confused by proof of correctness of Majority
At each step,

if $c == 0$, set $c=1$.
Otherwise, if $c&gt;0$, either increment $c$ or decrement $c$.

Since $c$ is 0 initially, it is always true that $c\ge0$. That means, $-c\le0$ all the time.

Suppose, at some moment, $c'$ is positive. The definition of $c'$ says $c'=c$ when $a^*=v$ and $c'=-c$ otherwise. Since $-c\le0$, $c'\not=-c$. So, the situation cannot be &quot;otherwise&quot;. The situation must be other than &quot;otherwise&quot;, i.e, $a^*=v$ and, hence, $c'=c$.
We just proved that for any moment, if $c'$ is positive, then $a^*=v$ and $c=c'$ is also positive.
Now just apply the above conclusion to the very last moment.