van links naar rechts in het zwart

We hebben een $m*n$rechthoek bestaande uit $mn$ eenheidsvierkanten.
Ieder vakje wordt in het zwart of in 't wit gekleurd bij een partitie.
We definieren een pad als een opeenvolging van vierkanten betreden die zijden met elkaar gemeen hebben.
We noteren met $N$ het aantal manieren om het bord in wit en zwart te kleuren zodat er minimum $1$ pad bestaat uit enkel zwarte vierkanten die van het linkerdeel naar het rechtse deel van de rechthoek gaat.
$M$ is het aantal manieren waarbij er $2$ verschillende paden zijn in het zwart die van links $\to$ rechts gaan (dus geen zwart vierkant gemeen hebben)
Bewijs dat $N^2\ge 2^{mn}M$