I am asking this question to verify my thought process which involves using induction to solve a problem. I am sure there's a solution to this on MSE but I am asking this question to ascertain my thought process and to know if I am using induction correctly.
The following question is the problem number $3$ of IMO $1988$.
Question:
A function $f$ is defined on the positive integers by $$f(1) = 1,f(3) = 3$$ $$f(2n) = f(n)$$ $$f(4n + 1) = 2f(2n + 1) − f(n)$$ $$f(4n + 3) = 3f(2n + 1) − 2f(n)$$ for all positive integers $n$. Determine the number of positive integers $n$, less than or equal to $1988$, for which $f(n) = n$.
My thought process: Right off the bat, we can conclude that $f(2^k)=1$ for all positive integers $k$. Also, if $n=n_o \times 2^k$ where $n$,$n_o$, and $k$ are all positive integers, then $f(n)=f(n_o)$ assuming $n_o$ is odd. So it suffices to focus on just odd positive integers.
It is also very easy to show that $f(n)=n$ whenever $n$ differs by a power of $2$ by $1$. So we get a long list of numbers like $7,9,15,17$ etc. which satisfy the requirement of $f(n)=n$. The bizarre thing for me was that there are numbers like $21$ and $27$ which satisfy the given requirement.
Also, the more bizarre thing was that the value of the function for integers $n$ which do not satisfy the requirement of $f(n)=n$, seemed somewhat random. For instance, $f(11)=13$, and $f(19)=25$. Then I observed that $f(13)=11$ and $f(25)=19$ essentially suggesting that perhaps, $f(f(n))=n$.
Also, since the few solutions I could formalize had something to do with power of two, I started looking at binary expansion of numbers. Then it hit me. The binary expansion of $11$ is $1011$ and that of $13$ is $1101$. So this function takes the binary number and reverses the bits! So the final answer would be $92$, number of "binary palindromes" less than or equal to $1988$ :).
Here's my question. I can easily prove that this is indeed the case but that requires induction. Following is the statement for the induction statement.
Induction statement: For all integers $k<4n$, the given function $f(k)$ maps integers $k$ to integers obtained by reversing the bits in the binary expansion of the number $k$.
The function can be evaluated manually and we can ascertain the base case till, for instance, $n=4$. If we now have to prove this statement to be true for $n+1$, we'll have to essentially show that it is true for $k=4n+1$ and $k=4n+3$, as the other two numbers are covered by the base case once we remove a factor of $2$ from them.
The proof involves assuming a certain binary expansion for $n$, and showing that this is indeed true. In the proof, I'll need to assume that value of $f(2n+1)$ and $f(n)$ can be assumed to be as stated in the inductive statement as they are less than $4n$. It is quite easy and I am not giving an entire proof here because all I need to know is if the way I plan to use induction is right or wrong. Please let me know if I have defined the inductive step correctly.