How many Hashes to find a digest of 2^{n−k}? Given an n-bit cryptographic hash function $H$, how many messages should we expect to hash before  finding a message $x$ such that $H(x) &lt; 2^{n−k}$ for some integer k?

My take: Shouldn't it simply take on average $2^{n-k}/2$ to find the hash?
The expected number of hashes would be $2^k$.

Here's why: if we model the hash function as a random Oracle, then each distinct message would have probability $2^{-k}$ of satisfying $H(m) &lt; 2^{n-k}$.  The probability for each message is independent, and so the expected number of trials before you hit an event with probability $2^{-k}$ is $2^k$.