How to disprove that every odd number can be written in the form $2^n + p$ with $p$ prime?

It suffices to find a counterexample.

After some searching, we find A133122

Odd numbers which cannot be written as the sum of an odd prime and a power of two

$$1, 3, 127, 149, 251, 331, 337, 373, 509, 599, 701,\dots$$

Even allowing $n=0$ and the use of even primes to say $3=2^0+2$ and ignoring $1$, the smallest counterexample is apparently $127$.

To prove that $127$ is in fact a counterexample, note that $127 = 64+3^2\cdot 7 = 32+5\cdot 19 = 16 + 3\cdot 37 = 8+7\cdot 17=\dots$ and so no power of two is valid.

These numbers are named Obstinate Numbers.

A brief spreadsheet search on the primes gives $149$ as a counterexample.

$149-2^0 = 148$, even
$149-2^1 = 147 = 3\cdot7^2$
$149-2^2 = 145 = 5\cdot29$
$149-2^3 = 141 = 3\cdot47$
$149-2^4 = 133 = 7\cdot19$
$149-2^5 = 117 = 3^2\cdot13$
$149-2^6 = 85 = 5\cdot17$
$149-2^7 = 21 = 3\cdot7$

The smallest composite counterexample is $905$, the first member of the OEIS A098237.