A slice of size p p p buys a codeword of cost p p p, i.e.
H = i â â p i â lo g 2 â p i â 1 â = â i â â p i â lo g 2 â p i â .
Fix a length n n n and ask: how many strings of length exactly n n n are there?
Now ask: how many possible descriptions are shorter than n n n â that is, programs of length 0 , 1 , 2 , ⦠, n â 1 0, 1, 2, \dots, n-1 0,1,2,â¦,nâ1?
Adding them up gives1 + 2 + 4 + ⯠+ 2 â n â 1 = 2 n â 1 , 1 + 2 + 4 + \dots + 2^{\,n-1} = 2^n - 1, 1 + 2 + 4 + ⯠+ 2 n â 1 = 2 n â 1 ,which is one fewer than the number of strings.