I believe this can be done by fixing `k` and then using induction on `n` to get all pairs `(n,k),` but I don't immediately see how to do that, so I turned the discrete problem into a continuous one. Note that since everything is positive, we can take the kth root of each side to get the equivalent inequality
`2^(n/k)>n/k,` which should hold for all natural numbers k and n. This is obviously true if `n<=k,` since the left side will be greater than 1 and the right won't, so we only have to worry about when `n>k.` If we can prove that the inequality
holds for all real `x>1` (greater than 1 since `n>k`), then it will hold automatically for the rationals. Taking the derivative of both sides, note that `(ln 2)*2^x>1` whenever `x>1,` so the left side increases faster than the right. Also note that when `x=1,` `2^x>x,` so `2^x>x` for all rational `x` greater than or equal to 1, and we showed above also when `x<1.` This completes the (admittedly, probably not the best) proof.