Showing that $3/4$ of all words over $\{0,1\}^n$ have $K(w) \geq n-2$

Question

$K(n)$ is the kolmogorov-complexity of a word n. I know that for every $n$, there's at least one word $w_{n}$ of length $n$, such that $k(w_{n}) \geq n$. There's $2^n$ words in $\{0,1\}^n$, how can I continze from here?

Answer 1

We have $2^n$ different words of length $n$ over $\{0,1\}$. All the words with $K(w) < n-2$ are at most$\sum_{i=1}^{n-3} 2^i = 2^{n-2} -2$. So now looking for $K(w) > n-2$ we get $2^n - 2^{n-2}+2$ which is $3/4$ of all the words.