# Proving $v(s,p)=2^{p-1}(2s-1)$ is a bijection of natural numbers and $f(s)=2s-1$ is a bijection between natural numbers and odd numbers.

How do I prove this function is bijective? $$v(s,p)=2^{p-1}(2s-1).$$ The domain is natural numbers and the codomain is also the natural numbers.

And this one: $$f(s)=2s-1.$$ The domain is the natural numbers, and the codomain is the odd numbers in the natural numbers.

With this one I would do this to show it's injective: \begin{align} v(s)&=v(s_1)\\ \implies 2s-1&=2s_1-1\\ \implies (2s_1)/2&=(2s_2)/2\\ \implies s=s_1 \end{align} So it's injective since if $$v(s)=v(s_1)$$ then $$s=s_1$$.

And to show it's surjective $$f(s)=y$$: \begin{align} y&=2s-1\\ \implies s&=(y+1)/2 \end{align} Then the function must be surjective since every $$y$$ is the same as the codomain for $$f$$.

Am I correct?

• It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $\mathbb{R} \to \mathbb{R}$ but is not a bijection $\mathbb{Z} \to \mathbb{Z}$ (or $\mathbb{N} \to \mathbb{N}$). – Clive Newstead Dec 14 '18 at 14:42

For $$v(s, p)= 2^{p-1}(2s+ 1)$$, to show "injective" we have to show that if $$v(s_1,p_1)= v(s_2, p_2)$$ then $$s_1= s_2$$ and $$p_1= p_2$$. A crucial point is that $$2^{p-1}$$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".