Q:

How to prove that algorithm returns the value which appears more than $n/2$ times in the array?

Given the following algorithm (pseudocode):
alg1(A[1,..,n])
    i <- 1
    candidate <- NULL
    count <- 0
    while(i <= n)
        if(count = 0)
            candidate <- A[i]
            count <- count + 1
        else if(candidate = A[i])
            count <- count + 1
        else
            count <- count - 1
        i <- i + 1
    return candidate

I need to prove that if a value appears more than $n \over 2$ times (let the value be named $M$) in the array then it will be returned. 
$\mathbf{EDIT:}$ here's my 2 attempt. First we assume that the array $A$ contains at least 3 elements (if less then the proof is trivial). The element which appears more than $n/2$ times is $M$ else it's $M'$. Let a two-element combination of $MM'$ or $M'M$ be called $C$. Every time we traverse a $C$ the count decreases by one. 
CASE 1: If the pattern is strictly alternating combinations of type $C$  then the first and the last element must be $M$ (otherwise $M$ will not appear more than $n/2$ times) and this means that after the last iteration the candidate is $M$.
CASE 2: We can see that after any number of adjacent $C$'s the counter will be $0$ and the candidate will be either $M$ or $M'$. It is given that more than $n/2$ elements of $M$ do exist in the array, so the number of $C$ combinations must be supplemented by at least $1$ occurrence of $k$ adjacent elements of $M$ either before $C$'s or after $C$'s. If it's after, then the next candidate is $M$ and it will continue to be so as long as we keep traversing $k$ elements of adjacent $M$'s. If it's before than the count will be at least $1$ before it proceeds to iterate through $C$'s and essentially it'll behave just like CASE 1.
I'm still aware that the proof is not perfect but I feel like it's an improvement. Suggestions/advice is very welcome.

A:

Let us prove the following claim by induction:

Suppose that the first $i$ symbols contain $j$ copies of $\sigma$, and let $\delta = j-(i-j) = 2j-i$. After the $i$th iteration of the loop:
(a) If $\delta > 0$ then $candidate=\sigma$ and $count \geq \delta$.
(b) If $\delta \leq 0$ then either $candidate=\sigma$ or $count \leq -\delta$.

This certainly holds for $i = 0$. Given that it holds for $i$, we now show it holds for $i':=i+1$ as well. Let $j,j'$ be the number of copies of $\delta$ in the first $i,i'$ symbols (respectively), and let $\delta=2j-i$, $\delta'=2j'-i'$. Define $candidate,candidate'$ and $count,count'$ as the values of these variables after $i,i'$ iterations (respectively).
There are several cases to consider.
Case 1: the $i'$th symbol is $\sigma$.
Case 1a: $\delta > 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count+1 \geq \delta+1 = \delta'$.
Case 1b: $\delta = 0$, $candidate = \sigma$. This is the same as Case 1a.
Case 1c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$. Therefore $candidate' = \sigma$ and $count' = 1 = \delta'$.
Case 1d: $\delta < 0$ and $candidate = \sigma$. This is the same as Case 1a.
Case 1e: $\delta < 0$ and $candidate \neq \sigma$. The induction hypotehsis states that $count \leq -\delta$. Therefore either $candidate' = \sigma$, or $count' = count-1 \leq -(\delta+1) = -\delta'$.
Case 2: the $i'$th symbol is $\tau \neq \sigma$.
Case 2a: $\delta > 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count-1 \geq \delta-1 = \delta'$.
Case 2b: $\delta = 0$ and $candidate = \sigma$. If $count = 0$ then $count' = 1 = -\delta'$. Otherwise, $candidate' = \sigma$.
Case 2c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$, and so $count' = 1 = -\delta'$.
Case 2d: $\delta < 0$ and $candidate = \sigma$. This is the same as Case 2b (with $1 \leq -\delta'$ in the first case).
Case 2e: $\delta < 0$ and $candidate \neq \sigma$. If $candidate = \tau$ then $count' = count + 1 \leq -(\delta-1) = -\delta'$. If $candidate \neq \tau$ then $count' = 1 \leq -\delta'$.

Given the claim, we see that if $\sigma$ appears more than $n/2$ times, then when $i=n$ we have $\delta > 2(n/2)-n > 0$, and so $candidate = \sigma$.

