Prove by induction that for all $n \geq 3$: $n^{n+1} > (n+1)^n$

Sometimes the trick is to write the problem in a different form.

The inequality is equivalent to

$$\left(1+\frac{1}{n}\right)^n < n$$

The inductive step follows this way:

$$ \left(1+\frac{1}{n+1}\right)^{n+1} < \left(1+\frac{1}{n}\right)^{n+1}= \left(1+\frac{1}{n}\right)^{n}\left(1+\frac{1}{n}\right)$$

Use P(n) and you are done....

Suppose that the claim holds for $n$, so we have $$n^{n+1} > (n+1)^n$$

For a proof by contradiction, suppose that the claim fails for $n+1$, so we have: $$(n+2)^{n+1} \geq (n+1)^{n+2}$$

Mulpitlying these two inequalities gives: $$ (n^2 + 2n)^{n+1} = (n(n+2))^{n+1} > (n+1)^{2n+2} = (n^2+2n+1)^{n+1}$$ Clearly, this is impossible. So, the claim for $n+1$ has to hold as well.

Hint: What about trying to show an equivalent inequality $n>\left(1+\frac1n\right)^n$ for $n\ge 3$ instead?

Spoiler:

$1^\circ$ It holds for $n=3$, since $3>\frac{4^3}{3^3}=\frac{64}{27}=2+\frac{10}{27}$.
$2^\circ$ Assume that it holds for $n$. Then $n+1=n\left(1+\frac1n\right) > \left(1+\frac1n\right)\left(1+\frac1n\right)^n = \left(1+\frac1n\right)^{n+1} > \left(1+\frac1{n+1}\right)^{n+1}$.