Polynomial over characteristic two finite field of odd degree with certain image I am trying to construct a polynomial $f \in \mathbb{F}_{2^k}$ of odd degree, such that $\forall x \in \mathbb{F}_{2^k} \exists \alpha \in \mathbb{F}_{2^k}$ such that $f(x)=\alpha ^2 -\alpha$. 
Working with some normal basis $\{ \alpha ^{2^i} | 0 \le i \le k-1 \}$, the image of $x \to x^2 -x$ is $\{ \sum c_i \alpha ^{2^i} | \sum c_i = 0, c_i \in \mathbb{F}_{2} \}$. In other words, we require $f(\mathbb{F}_{2^k}) \subseteq Im(t^2-t)$, and this image is a subspace of dimension $k-1$ of the field.
It is easy to construct such $f$ of even degree: $f(x)=x^{2^{i+1}} - x^{2^i}$, for any $i$.
EDIT: I managed to find an example, but I don't like it much: taking $f(x) = x^{2^k + 1} - x$. For every $x \in \mathbb{F}_{2^k}$, $f(x)=x^2-x$.
 A: Another way to state your condition is that, for every $\beta \in \mathbf{F}_{2^k}$, $f(\beta)$ has trace 0 over $\mathbf{F}_2$.
For $k=5$, an example is $f(x) = x^9 - x^5$. To see that this has trace 0 for any $\beta \in \mathbf{F}_{32}$:
$$ \begin{align*} \mathop{Tr}(\beta^9 - \beta^5) 
&= 
\mathop{Tr}(\beta^9) - \mathop{Tr}(\beta^5)
\\&=
(\beta^9 + \beta^{18} + \beta^{36} + \beta^{72} + \beta^{144})
- (\beta^5 + \beta^{10} + \beta^{20} + \beta^{40} + \beta^{80})
\\&=
(\beta^9 + \beta^{18} + \beta^{5} + \beta^{10} + \beta^{20})
- (\beta^5 + \beta^{10} + \beta^{20} + \beta^{9} + \beta^{18})
\\&= 0 \end{align*}
$$
In general, the condition means that
$$ f(\beta) + f(\beta)^2 + \cdots + f(\beta)^{2^{k-1}} = 0 $$
for every $\beta \in \mathbf{F}_{2^k}$, or equivalently,
$$ f(x) + f^\sigma(x^2) + f^{\sigma^2}(x^4) + \cdots + f^{\sigma^{k-1}}(x^{2^{k-1}}) \equiv 0 \pmod{ x^{2^k} - x} $$
where $f^\sigma$ is the polynomial formed by conjugating each coefficient of $f$ by the action $u \mapsto u^2$.
We can split the powers of $x$ into orbits under the action $x \mapsto x^2 \pmod{x^{2^k} - x}$ -- i.e. writing
$$ f(x) = u + h(x) (x^{2^k} - x) + \sum_m g_m(x^m) $$
where $u$ is a constant with trace 0, and each $g$ has the form
$$g(x) = \sum_{j=0}^{k-1} c_j x^{2^j}.$$
Each $g(x)$ must satisfy the constraint, and any choice of valid $g's$ gives a valid $f$. So,
$$0 \equiv \sum_{i=0}^{k-1} g^{\sigma^i}(x^{2^i})
\equiv \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} c_j^{2^i} x^{2^{i+j}}
= \sum_{j=0}^{k-1} x^{2^{j}} \sum_{i=0}^{k-1}  c_{j-i}^{2^{i}} 
\pmod{x^{2^k} - x}
$$
(there was a change of variable $j \mapsto j-i$) where the index on $c$ is taken modulo $k$. Each coefficient gives the same condition:
$$\sum_{i=0}^{k-1} c_{k-1-i}^{2^i} = 0$$
Now, how can we use this to find a polynomial of small, odd degree? Consider $k=5$. One of the orbits of powers of x is:
$$ x^5, x^{10}, x^{20}, x^{40} \equiv x^9, x^{80} \equiv x^{18} $$
By setting the coefficients on $x^9$ and a smaller term to $1$ and the rest to $0$ will satisfy the equation. This is the example at the top of my answer.
