O(n) = a*n
じゃなくて
O(n) = f(n) where 定数 a が存在し全ての n に対し f(n)/n < a
とすれば

T(n) - 2*T(n/2) = f(n)
2*T(n/2) - 4*T(n/4) = 2*f(n/2)
4*T(n/4) - 8*T(n/8) = 4*f(n/4)
...
(n/2)*T(2) - n*T(1) = (n/2)*f(2)

T(n) - n*T(1) = f(n) + 2*f(n/2) + 4*f(n/4) + ... + (n/2)*f(2)
T(n) - n*T(1) = n*(f(n)/n + f(n/2)/(n/2) + f(n/4)/(n/4) + ... + f(2)/2)
T(n) - n*T(1) < n*a*log2(n)