Very interesting problem that puzzles me

[jdp]

One of my friends showed me this problem and I've been thinking about it all day. It's something like if f(2x) is equal to f(f(y)) and that f(2y) + 1 is f(2y +1) and f(0) is 0, what is f(n). It seems very maclaurin esque to me but... anyway... first post and pretty nice problem. Would love help figuring this beast out.

 

[Simon Bridge]

Number them:
1. f(2x)=f(f(y))
2. f(2y)+1=f(2y+1)
3. f(0)=0

guessing: x,y,n are integers?
are x and y specific numbers or is just any arbitrary number?
i.e. does this also hold: $f(2x+1)=f(2x)+1$ ?

If so then I'd start from the observations:

#1 tells you f(f(n))=f(some even number).
#2 (with #3) tells you that if n is odd, then f(n)=f(n-1)+1

 

[jfgobin]

That looks weird. Are you sure there isn't something missing?

By #3, f(0)=0, using y=0, by #2, f(1)=1. Using 2y=1 and #2 again, f(2)=2, and so forth.

So at least for x \in \mathbb{N}, f(x)=x.

 

[pwsnafu]

I think OP's problem is the following:

Find $f : \mathbb{N} \to \mathbb{N}$ satisfying

1. $f(0) = 0$,
2. For each $k \in \mathbb{N}$ we have $f(2k) = f(f(k))$,
3. For each $k \in \mathbb{N}$ we have $f(2k+1) = f(2k) + 1$.

At the very least it prevents the trivial solution.

Note: I'm including 0 in the naturals for this problem.

 

[jdp]

Yes, I clarified. Exactly like this. I just don't know where to start

 

[Simon Bridge]

Have you had a play with the relations, looking at different numbers?

Using pwsnafu's formulation in post #4:

If $f^{-1}\big ( f(k)\big )=k$ is the inverse function in action,
then, from #2:

$f^{-1}\big ( f(2k)\big ) = f^{-1}\big ( f(f(k)\big ) \\ \Rightarrow f(k)=2k$​

But that does not fit the other clues.

Notice: 2k is always even, 2k+1 is always odd.
... so the clues are telling you what happens in the case of odd or even n.

This is how you go about exploring mathematical relations - you end up making a list of things that the relations are telling you.
It's important that you get used to this process - after a bit you spot a pattern that looks likely and you set out to prove it.

eg.
What happens when you apply the formula to k=0?
What is f(f(2k))? f(f(2k+1))?

 

[HallsofIvy]

I think OP's problem is the following:

Find $f : \mathbb{N} \to \mathbb{N}$ satisfying

1. $f(0) = 0$,
2. For each $k \in \mathbb{N}$ we have $f(2k) = f(f(k))$,
3. For each $k \in \mathbb{N}$ we have $f(2k+1) = f(2k) + 1$.

At the very least it prevents the trivial solution.

Note: I'm including 0 in the naturals for this problem.

Start by doing the obvious calculations. 1 is odd: 1= 2(0)+ 1 so f(1)= f(2(0)+ 1)= f(2(0))+ 1= f(0)+ 1= 1. 2 is even: 2= 2(1) so f(2)= f(f(1))= f(1)= 1. 3 is odd: 3= 2(1)+ 1 so f(3)= f(2(1)+ 1)= f(2(1))+ 1= f(2)+ 1= 1+ 1= 2. 4 is even: 4= 2(2) so f(4)= f(2(2))= f(f(2))= f(1)= 1. 5 is odd: 5= 2(2)+ 1 so f(5)= f(2(2)+ 1)= f(2(2))+ 1= f(4)+ 1= 1+ 1= 2.

You should be able to see a very easy pattern for f(n) when n is even and for f(n) when n is odd. And then use "proof by induction" to show that you are correct.