# Proving the existence of $[2k, k, k]$-codes

I'm trying to prove that for a $[2k, k, k]$-code, the Griesmer bound does not hold for $k > 4$.

Griesmer bound For any linear $[n, k, d]-$code over $\mathbb{F}^k_2$ the following holds: \begin{equation} n \ge \displaystyle\sum_{i=1}^{k}\left\lceil \frac{d}{2^{i-1}} \right\rceil. \end{equation}

$\lceil x \rceil$ is the ceiling function, so $\lceil x \rceil$ is the smallest integer $m$ with $m \ge x$.

So I'm trying to prove that for any $k > 4$ we have that \begin{equation} 2k < \sum_{i=1}^{k} \left\lceil \frac{k}{2^{i-1}} \right\rceil \end{equation}

I've tried doing it with induction, but this doesn't bring me very far. I'm puzzling with the fact that $\frac{k}{2^i} \le 1$ for a large $i$, but I can't quite seem to find anything helpful to give a definite proof.

Let us separate it into two cases :

Case 1 : $k$ is not the form $2^r$

Let us define $m:=\lceil\log_2(k)\rceil-1$ where we have $2^m\lt k\lt 2^{m+1}$.

Then, $$2^{m-i+1}\lt \frac{k}{2^{i-1}}\lt 2^{m-i+2}$$

So, \begin{align}\sum_{i=1}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil&=\sum_{i=1}^{m+1}\left\lceil\frac{k}{2^{i-1}}\right\rceil+\sum_{i=m+2}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil\\\\&\ge\sum_{i=1}^{m+1}(2^{m-i+1}+1)+\sum_{i=m+2}^{k}1\\\\&=2^{m+1}-1+m+1+k-(m+2)+1\\\\&=2^{m+1}-1+k\\\\&\gt 2k-1\end{align} Since $\sum_{i=1}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil$ is an integer, we are done.

Case 2 : $k=2^m$

\begin{align}\sum_{i=1}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil&=\sum_{i=1}^{m+1}\left\lceil\frac{2^m}{2^{i-1}}\right\rceil+\sum_{i=m+2}^{2^m}\left\lceil\frac{2^m}{2^{i-1}}\right\rceil\\\\&=\sum_{i=1}^{m+1}2^{m-i+1}+\sum_{i=m+2}^{2^m}1\\\\&=2^{m+1}-1+2^m-(m+2)+1\\\\&=2k+(k-\log_2k-2)\\\\&\gt 2k\end{align} Here, we used $$k-\log_2k-2\gt 0\tag1$$ for $k\ge 5$.

Finally, let us prove $(1)$ for $k\ge 5$.

Let $f(k)=k-\log_2k-2$.

Then, $$f'(k)=1-\frac{1}{k\ln 2}=\frac{k\ln 2-1}{k\ln 2}\gt 0$$ So, $f(k)$ is increasing with $f(5)=3-\log_2(5)\gt 3-\log_2(8)=0$.

It follows from this that $f(k)\gt 0$ for $k\ge 5$.