$2^\kappa-\kappa=2^\kappa$ for infinite $\kappa$ without the AC Without using the AC, show that if $\kappa \geq \aleph_0$ then $2^{\kappa}-\kappa=2^{\kappa}$. That is to say, for such $\kappa$ there is a unique cardinal $\mu$ such that $\kappa+\mu=2^{\kappa}$, and this $\mu$ equals $2^{\kappa}$.
In Rubin & Rubin, "Equivalents of the Axiom of Choice", 2nd edition, 1985, this is mentioned as a well-known property of cardinals (cf. Theorem 0.14.f in the book), but sadly they do not provide a proof.
Found a proof for the case $\kappa=2\kappa$.
Lemma: for any cardinals $\kappa,\mu,\lambda$, if $\kappa+\mu=\lambda=\lambda^{2}$ then either there is a surjection of $\kappa$ onto $\lambda$, or we have $\mu=\lambda$.
Proof: if $f:\kappa\sqcup\mu\to\lambda^{2}$ is a bijection (with $\sqcup$ denoting disjoint union), let $g:\kappa\to\lambda$ be the map $\pi_1\circ (f\upharpoonright\kappa)$, where $\pi_{1}:\lambda^{2}\to\lambda$ is the projection on the first factor (i.e. $\pi_{1}(x,y)=x$ for $x,y\in\lambda$). If $g$ is surjective, we are done. If not, $\exists{z\in\lambda}$ such that $(\{z\}\times\lambda)\cap f[\kappa]=\varnothing$. But then we have $\{z\}\times\lambda\subseteq f[\mu]$, since f is a surjection, and so $\lambda\leq\mu$; since $\mu\leq\lambda$ also holds, we find $\mu=\lambda$, q.e.d.
Now if $\kappa+\mu=2^{\kappa}$, for a $\kappa$ with $\kappa=2\kappa$, apply the Lemma with $\lambda=2^{\kappa}$; one has $\lambda=\lambda^{2}$ in view of $\kappa=2\kappa$, and a surjection of $\kappa$ onto $\lambda=2^{\kappa}$ cannot exist (Cantor). It follows that $\mu=2^{\kappa}$.
 A: The most difficult part would be to show that $2^\kappa \leq \mu$ if $\kappa + \mu = 2^\kappa =2 \times 2^\kappa$. It can be easily reduced to the following lemma:
Lemma Let $X$ be a set and $f \colon X \rightarrowtail 2 \times \mathcal{P}(X)$ be an injection, where $2 = \{0, 1\}$. Then there exists an injection $g \colon \mathcal{P}(X) \rightarrowtail 2 \times \mathcal{P}(X)$ such that $\mathop{\mathrm{Im}}f$ and $\mathop{\mathrm{Im}}g$ are disjoint.
(Injectivity of $f$ is not necessary)
Proof Let $\pi_2 \colon 2 \times \mathcal{P}(X) \to \mathcal{P}(X)$ be the right projection.
Define $g$ by
$$ g(A) = \begin{cases}
(1,A) & \text{if}\; (1, A) \notin \mathop{\mathrm{Im}} f \\
(0,\{ x \in X : x \notin \pi_2(f(x)) \;\text{xor}\; f(x)=(1,A) \}) & \text{if}\; (1, A) \in \mathop{\mathrm{Im}} f.
\end{cases} $$
Here $P \;\text{xor}\; Q$ means that $P$ but not $Q$, or $Q$ but not $P$.
(The intuition here is that we basically want to define $g(A) = (1, A)$. When it's impossible, then we want somewhere in $(0, -)$ to escape to. The existence of such a place is guaranteed by the diagonal argument, but we have to choose a different place for each collision. Xor-ing with $f(x)=(1, A)$ is the trick here: it embeds information about $y$ such that $f(y)=(1, A)$, while not disturbing the diagonal argument.)
$\mathop{\mathrm{Im}}f$ and $\mathop{\mathrm{Im}}g$ are disjoint. To show this, assume that $f(y) = g(A)$. If $(1, A) \notin \mathop{\mathrm{Im}} f$, then $f(y) = g(A) = (1, A)$. It contradicts with $(1, A) \notin \mathop{\mathrm{Im}} f$. If $(1, A) \in \mathop{\mathrm{Im}} f$, then $f(y) = (0, \mathop{-}) \neq (1, A)$. Thus
\begin{align*}
y \in \pi_2(f(y))
& \iff y \in \pi_2(g(A)) \\
& \iff y \in \pi_2((0,\{ x \in X : x \notin \pi_2(f(x)) \;\text{xor}\; f(x)=(1,A) \})) \\
& \iff y \in \{ x \in X : x \notin \pi_2(f(x)) \;\text{xor}\; f(x)=(1,A) \} \\
& \iff y \notin \pi_2(f(y)) \;\text{xor}\; f(y)=(1,A) \\
& \iff y \notin \pi_2(f(y))
\end{align*}
leads to contradiction. Therefore we never have $f(y) = g(A)$.
$g$ is injective. To show this, assume that $g(A) = g(A')$. Then either $(1, A), (1, A') \notin \mathrm{\mathop{Im}} f$ or $(1, A), (1, A') \in \mathrm{\mathop{Im}} f$. In the former case, we have $(1, A) = g(A) = g(A') = (1, A')$ and thus $A = A'$. In the latter case, take $y$ such that $f(y) = (1, A)$. Expanding $y \in \pi_2(g(A)) \iff y \in \pi_2(g(A'))$, we obtain
$$ y \notin \pi_2(f(y)) \;\text{xor}\; f(y) = (1, A) \iff y \notin \pi_2(f(y)) \;\text{xor}\; f(y) = (1, A')$$
and, since $\text{xor}$ is cancellative, we have
$$ f(y) = (1, A) \iff f(y) = (1, A'). $$
Since the left hand side is true, the right hand side is. Since $(1, A) = f(y) = (1, A')$, we have $A = A'$.
□
Thanks to alg_d (the author of the famous Japanese website about AC) for letting me know this interesting problem.
A: A proof of this theorem

THEOREM $1$. We are able to prove without the aid of the axiom of choice that if $\mathfrak m$ is a cardinal number $\ge\aleph_0,$ then
  $$2^\mathfrak m-\mathfrak m=2^\mathfrak m.$$

takes up most of pp. 172–173 in W. Sierpiński's book Cardinal and Ordinal Numbers, Second Edition Revised, 1963. Sierpiński uses the following lemma:

LEMMA. If $\mathfrak m,\mathfrak p,\mathfrak s$ are cardinal numbers such that $2^\mathfrak m=\mathfrak m+\mathfrak p$ and $\mathfrak m=\mathfrak m+\mathfrak s,$ then $\mathfrak p\ge2^\mathfrak s.$

According to Sierpiński the theorem is due to A. Tarski, who stated it without proof in 1926; a proof was published by Sierpiński in: W. Sierpiński, Démonstration de l'égalité $2^\mathfrak m-\mathfrak m=2^\mathfrak m$ pour les nombres cardinaux transfinis, Fund. Math. 34 (1947), 113—118.
A: You can prove it this way : 
$2^\kappa \leq 2^\kappa + \kappa \leq 2^\kappa + 2^\kappa \leq 2^\kappa \times 2 \leq 2^{\kappa+1}\leq 2^\kappa$
The first inequality comes from the natural injection, 
The second as well,where there is an injection $\kappa \to 2^\kappa$, sending $x\to \{x\}$
The third one comes from identifying the disjoint union of $A$ and $B$ as $A\times\{0\}\cup B\times\{1\}$
The fourth one is the natural injection,
And the last one is simply that, $\kappa$ being infinite, $\kappa +1 \leq \kappa$.
By Cantor-Bernstein's theorem, all these inequalities of cardinals (i.e. injections) can be turned into equalities of cardinals, that is, bijections.
Therefore $2^\kappa +\kappa \sim 2^\kappa$ 
Now if you take $A$ to be a subset of $2^\kappa$ of cardinality $\kappa$, then you can use this bijection to produce a bijection $2^\kappa \setminus A\to 2^\kappa$.
EDIT : It seems Noah Schweber was quicker
Second edit: The last sentence of this answer is there to show the uniqueness of $\mu$: assume $\kappa + \mu = 2^\kappa$. Then the image of $\kappa$ under a bijection $\kappa + \mu \to 2^\kappa$ is a subset $A\subset 2^\kappa$ of cardinality $\kappa$. But $2^\kappa\setminus A$ is the image of $\mu$ o has cardinality $\mu$. But according to my last sentence it also has cardinality $2^\kappa$, which proves that $2^\kappa \sim \mu$. I'm adding this to my answer because Matthé Van der Lee commented on Noah's answer saying that the uniqueness of $\mu$ hadn't been established.
A: By contradiction: $2^\kappa-\kappa=[\kappa,2^\kappa)$. If $|[\kappa,2^\kappa)|<2^\kappa$ then, because $2^\kappa=[0,2^\kappa)=[0,\kappa)\cup[\kappa,2^\kappa)$, we must have $2^\kappa=|[0,\kappa)|=|\kappa|=\kappa$.
