Consider the language
$$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$
and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be bounded by
$$K(x_n) \leq c + 2\log_2 |x_n|$$
for some constant $c$.
My ideas :
(please note that I'm not writing this in a formal way, I am neglecting some constants/factors)
we want to be able to compress the string given by x_n above, thus we could set :
$$K(x_n) = K(1^i) + K(0^j) + K(1^k)$$
(to do this compression I evaluate that only i, j and k need to be compressed, thus we only consider the length of the binary representation of i,j and k as the upper-bound of their corresponding Komolgorov Complexity)
$$ \leq log_2 (i) + log_2 (j) + log_2 ((i+j)/2) + C$$
$$ = log_2 (i) + log_2 (j) + log_2 (i+j) - 1 + C$$
$$ = log_2 (i^2j + ij^2) + K$$
Now we might want to evaluate the length of X_n $$|x_n| \leq i + j + k = i + j + (i + j)/2$$
now to show the supposition we just need to show that :
$$ log_2 (i^2j + ij^2) \leq 2log_2 |x_n| = log_2 (|x_n|^2) $$
and this is where I get stuck