For $f:\mathbb{N}\to\mathbb{N}$ with $f(1)=1$, $f(2n)=f(n)$, $f(2n+1)=f(n)+f(n+1)$, show that the range of $f$ is $\mathbb{N}$

Question

Question: A function $f : ℕ \rightarrow ℕ$ is defined by $f(1)=1$, and for all $n\geq 1$, $$f(2n)=f(n)$$ $$f(2n+1)=f(n)+f(n+1)$$ Prove that the range of $f$ is $ℕ$.

Thoughts: I was first thinking to prove this by showing that the first function will always yield a positive integer because f(2) = 1 and it is only defined by f(1)=1, meaning if it is a negative number of decimal, it won't work. Also, I was guessing that the first function was for even numbers. But... I got a little stuck on proving the range for the second function. Using the same logic as before, I presumed that the second function was meant for odd numbers as any odd number can be represented by 2n+1. However, I don't know how to properly show that the range is only restricted to natural numbers as I'm guessing I can't simply say that it is not defined when it is anything but a natural number.

Am I going in the wrong direction with my thinking?

Any help would be extremely appreciated!

Answer 1

If $f(2^n +1)=n+1$ for all $n$, we get

$$\{2,3,4,...\} \subseteq f( \mathbb N).$$

Since $f(1)=1$ we derive

$$\mathbb N =\{1,2,3,4,...\} \subseteq f( \mathbb N).$$

From $f( \mathbb N) \subseteq \mathbb N$ we then conclude that $f( \mathbb N) =\mathbb N$ .

Answer 2

note that $0 \in \mathbb{N}$, and $f(0)=0$. also every positive integer can be written uniquely as $2^nk$ for $n \in \mathbb{N}$ and $k \in \{1,3,5,\dots \}$

it is easy to show that $f(2n+1) - f(2n-1) = f(n+1) - f(n-1)$ from which for every odd $k$:

$$ f(2^n k +1) - f(2^n k - 1) = f(k+1) - f(k-1) $$

and the RHS is zero unless $k=1$