Let $s(n)$ a function such that $s(n)\le \frac{2^n}{10n}$ for every $n$.  Prove that there's a series of circuits: $g_n: \{0,1\}^n\to \{0,1\}$ such that $g_n$ doesn't have a size $s$ circuit, but does have a size $s + O(n)$ circuit.I already proved a lemma which shall lead to the solution: let two boolean functoins $g, f: \{0,1\}^n \to \{0,1\}$ such that $f,g$ differ only for one input. If $f$ has a circuit of size $s$, then there's a circuit of size $s + O(n)$ for $g$.I'm not sure how to utilize this lemma for the circuits hierarchy theorem and be glad for help.  (*) We've seen in class Shannon's theorem.
Hierarchy theorem for circuits
complexity theory;circuits