I am trying to show that $f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$, where $f(a,b)=2^a (2b+1)-1$, is surjective using induction (possibly strong induction). In the case $n=0$, it is easy to see that $(0,0)$ does the trick.
Suppose there exist elements of $\mathbb{N}\times\mathbb{N}$ which map to each $n\in\{0,1,\dots,k\}$, consider the case $k+1$.
All I have is: $k+1=f(x,y)+1$ for some $(x,y)\in\mathbb{N}\times\mathbb{N}$, but I do not know how to continue. Any help is appreciated, thank you.
It is more convenient to show that every positive integer $n$ can be represented in the form $2^a(2b+1)$, where $a$ and $b$ are nonl-negative integers. We use strong induction. The result is clearly true for $n=1$. Let us suppose it is true for all $k\lt n$, and show it is true for $n$.
Perhaps $n$ is odd, say $2b+1$. Then we can take $a=0$.
Perhaps $n$ is even, say $n=2m$. By the induction hypothesis, there exist natural numbers $a_1$ and $b$ such that $m=2^{a_1}(2b+1)$. Then $n=2^a(2b+1)$, where $a=a_1+1$.