Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(n)+2f(f(n))=3n+5$

Question

Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $$f(n)+2f(f(n))=3n+5$$

---

In the book, the following solution is provided. For this post, only Case 1 is relevant.

From $f(1)+2f(f(1)) = 8$ we deduce that $f(1)$ is an even number between 1 and 6, that is, $f(1)=2, 4,$ or $6$.

$\textbf{Case 1:}$ If $f(1) = 2$ then $2+2f(2) = 8$, so $f(2) = 3$. Continuing with $3+2f(3) = 11$, we obtain $f(3)=4$, and formulate the conjecture that $f(n)=n+1$ for all $n \geq 1$. And indeed, in an inductive manner we see that $f(n)=n+1$ implies $n+1+2 f(n+1)=3 n+5$; hence $f(n+1)=n+2$

$\textbf{Case 2:}$ $f(1)=4$ gives $4+2 f(4)=8$, so $f(4)=2$. But then $2+2 f(f(4))=17$, which cannot hold for reasons of parity.

$\textbf{Case 3:}$ If $f(1)=6$, then $6+2 f(6)=8$, so $f(6)=1$. This cannot happen, because $f(6)+2 f(f(6))=1+2 \cdot 6$, which does not equal $3 \cdot 6+5$.

We conclude that $f(n)=n+1, n \geq 1$, is the unique solution to the functional equation.

$\textbf{My Doubt:}$ In Case 1, they claimed $f(n)=n+1$, and used induction to prove it. But how are they sure there doesn't exist other solutions? Induction doesn't prove that it's the only solution available with $f(1) = 2$ and $f(2) = 3$.

Answer 1

They don't show that $f(n)=n+1$ satisfies the conditions but rather that for each $n$, $f(n)$ HAS TO BE $n+1$. Here is how it works.

We have $f(1)=2$. That gives us \begin{align}2+2f(2)=\ \ 8&\implies f(2)=3\\ 3+2f(3)=11&\implies f(3)=4\\4+2f(4)=14&\implies f(4)=5\end{align} and so on. The point is that $f(n)=n+1$ for some $n$ forces $f(n+1)=n+2$. So since it is true for $n=1$, it has to be true for $n=2$, $n=3$ and so on for each $n$ inductively.

Hope this helps. Ask anything if not clear. :)

Answer 2

Yes, induction does prove the point, let us set for $n$ the property:

$$P(n): f(n) = n+1$$

Let us take $n$ s.t. $P(n)$ is true, then $f(n) + 2 f(f(n)) = 3n +5$, thus $n+1 + 2f(n+1) = 3n+5$ (just replace $f(n)$ by its value). You have then $2f(n+1) = 2n + 4$ so $f(n+1) = n + 2 = (n+1) +1$. So $P(n+1)$ is true.

Since $P(1)$ is true you have your point proven by induction.

If you don't get how this proves induction, add more information in your $P(n)$, for example

$$P(n): (n+1)_n \text{ is the only sequence of integers satisfying the functional equation for }k \leqslant n \text{ and such that } f(1) = 2.$$

The real context for induction is really rigid (even my second statement may not fit) it follows from the axioms of set theory. A piece of advice: if you are a new math student, don't break bad by thinking about it over and over again, it is indeed very abstract and precise; you can do that later if you specialize in logic, set theory or category theory...

Answer 3

These problems tend to have a solution of the form $f(x)=\frac{ax+b}{cx+d}$. Since we're only interested in integers we can try with the assumption that the numerator is 1.

$f(x)=ax+b$

$f(n)+2f(f(n))=3n+5$

$an+b+2[a(an+b)+b]=3n+5$

$an+b+2a^2n+2ab+2b=3n+5$

$an+3b+2a^2n+2ab=3n+5$

$(2a^2+a)=3$ $3b+2ab=5$

$a=1$.

$b=1$.

$f(n)=n+1$