Prove that $|A\cup B|^{n}+|A∩B|^{n}≥|A|^{n}+|B|^{n}$ Let $A, B, C$ three finite sets and $n$ is a natural number nonzero. We denote $| X |$ the cardinal of set $X$. Prove that $$|A\cup B|^n +|A\cap B|^n \geq |A|^n +|B|^n.$$
Since the statement is well known for $n = 1$ it is natural to use mathematical induction, but it is difficult to make the transition from $P (n)$ to $P (n +1)$. Any idea how to do this?
 A: Hint: Reduce to showing that:
$$(k+l-m)^n + m^n \ge k^n + l^n$$
for $m \le k,l$. What do you know about maximizing $x^n + y^n$ for fixed values of $x+y$?

I have no idea how to prove the identity using induction.
A: Note that
$$|A \cup B| -|A|= |B|- |A \cap B|=: a$$
You need to prove that
$$|A \cup B|^n -|A|^n= |B|^n- |A \cap B|^n$$
If $(A \cap B)=x$ and $|A|=y$ you need to prove that
$$x \leq y \Rightarrow  (x+a)^n-x^n\leq (y+a)^n-y^n $$
This follows immediately from the binomial theorem. If you want to use induction, check $P(1)$ and $P(2)$ [or better $P(0)$ and $O(1)$] and  the inductive step is the following:
From $P(n)$ we get
$$(x+a)^n-x^n\leq (y+a)^n-y^n \Rightarrow a\left((x+a)^n-x^n\  \right) \leq a \left( (y+a)^n-y^n \right) \Rightarrow \\
(x+a-x)\left((x+a)^n-x^n\  \right) \leq (y+a-y) \left( (y+a)^n-y^n \right)\Rightarrow \\
(x+a)^{n+1}-x^{n+1} -(x+a)x \left((x+a)^{n-1}-x^{n-1}\right)\leq (y+a)^{n+1}-y^{n+1} -(y+a)y \left((y+a)^{n-1}-y^{n-1}\right) $$
From $P(n-1)$ we get
$$ (x+a)^{n-1}-x^{n-1}\leq (y+a)^{n-1}-y^{n-1}\Rightarrow \\ (x+a)x \left((x+a)^{n-1}-x^{n-1}\right)\leq (y+a)y \left((y+a)^{n-1}-y^{n-1}\right)  $$
Ad these two together and you are done...
