4

I found this problem in an old textbook of mine and am unsure how to solve it. This was in a chapter about functions. Any help will be appreciated.

The Problem:

If $f: \mathbb{N} \to \mathbb{N}$ is a strictly increasing function such that $f(f(x)) = 2x+1$ for all natural numbers $x$. Solve for $f(13).$

Edit:

To show my work- I have tried manually guess and checking functions for $f(x)$, especially functions similar to $x^{x-1}$ and variations. None of these functions seem to work. I also tried finding linear functions for $f(x)$. If it is linear I believe it would be similar to $f(x) =x \sqrt2 + c$ where $c$ is a constant I am yet to ascertain.

user687894
  • 89
  • 5
  • 2
    What did you try? Please show your attempts. – Lion Heart Aug 09 '21 at 13:38
  • 4
    This might be a good time to review our guidelines for how to ask a good question, with emphasis on providing context. Your post is simply a question-in-the-title without no context provided, such as what attempts you made to solve the problem, where you got stuck. – Lee Mosher Aug 09 '21 at 13:38
  • Tried to add some context. I have not posted many times before so feel free to tell me if I need to make edits. – user687894 Aug 09 '21 at 13:42
  • 1
    Regarding your linear guess, is the function $\mathbb R\to\mathbb R$? If it is, the problem has multiple solutions. – Rushabh Mehta Aug 09 '21 at 13:45
  • I just updated the question with more information – user687894 Aug 09 '21 at 13:50
  • 3
    Please use mathjax, https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference to properly format the mathematical part of the text. Often, simply putting the formulas between dollars brings a better display, for instance instead of f(f(x))=2x+1 (with a final closing parenthesis) you may type $f(f(x)) = 2x+1$, which is shown like $f(f(x)) = 2x+1$. For the natural numbers try the font \Bbb N, so $\Bbb N$ is shown like $\Bbb N$. Could you please edit ... ?! – dan_fulea Aug 09 '21 at 13:59
  • 1
    OK, somebody else did the job... – dan_fulea Aug 09 '21 at 14:00
  • Thank you for the tip dan_fulea. Will do this from now onwards for future edits. – user687894 Aug 09 '21 at 14:00
  • 2
    Is $0$ in $\Bbb N$? – dan_fulea Aug 09 '21 at 14:02
  • 1
    @DonThousand ... well, i am just asking, the next question is what may be $f(0)$, respectively what may be $f(1)$... let us see first what is $\min\Bbb N$. (In my books, $\Bbb N$ is a monoid with the addition as operation.) – dan_fulea Aug 09 '21 at 14:05
  • @user687894 For some basic information about writing mathematics at this site see, e.g., here, here, here and here. – soupless Aug 09 '21 at 15:52

1 Answers1

4

Note that since $f(f(1))=3$ and $f$ is strictly increasing, $f(1)=2$ and $f(2)=3$. Thus, $f(3)=f(f(2))=5$. And, $f(5)=f(f(3))=7$. And, $f(7)=f(f(5))=11$. Thus, $f(11)=f(f(7))=15$.

So, $f(6)\in\{8,9,10\}$. If $f(6)=8$, then $f(8)=13$, which is not possible since $f(11)=15$, so $f(9)=f(10)=14$.

If $f(6)=10$, $f(10)=13$, which similarly would be a contradiction since $f(8)=f(9)=12$.

Thus, $f(6)=9$, so $$f(13)=f(f(f(6)))=2\cdot f(6)+1=19$$

Rushabh Mehta
  • 13,663
  • This definitely seems like the correct answer. I have created a table of values for the values of $f$(x) and this is around the correct range of number too. Thank you for all the help @Don Thousand – user687894 Aug 09 '21 at 14:56
  • 1
    May you please elaborate upon how you obtained $f(1)=2$ from $f(f(1))=3$ and $f$ being strictly increasing? – RiverX15 Aug 09 '21 at 14:57
  • @RiverX15 based on a previous answer from dicatemetokcus. https://imgur.com/a/biA88Dm – user687894 Aug 09 '21 at 15:06
  • @RiverX15 Note that since $f$ is strictly increasing, $f(x) \geq x$ for all $x$. We have $1 \leq f(1) \leq f(f(1)) = 3$. If $f(1) = 1$ then $f(f(1)) = f(1) = 1$; contradiction. If $f(1) = 3$ then $f(2) \geq 4$, so $3 = f(3) > f(2) \geq 4$; contradiction. So the only possibility is $f(1) = 2$. – Mark Saving Aug 09 '21 at 16:17
  • Very good answer $(+1)$! By the way to find $f(6)$ we could proceed as follow: We have $f(7)=11 , f(11)=15$ and since $f(x)$ is strictly increasing, $f(8)=12, f(9)=13, f(10)=14$. And Since $f(f(6))=13$ then $f(6)=9$. – Etemon Aug 09 '21 at 17:14
  • @Soheil Indeed, I noticed that after I wrote the solution, but was too lazy to rewrite. – Rushabh Mehta Aug 09 '21 at 17:18