2

I need to find all functions $f:\mathbb N^*\to\mathbb N^*$ that satisfy the relation: $$f(n)+2f(f(n))=3n+5.$$

Here $\mathbb N^*$ denotes the set of positive integers.
I have calculated that $f(1)=2$, $f(2)=3$, $f(3)=4$.

Observing from this pattern, I could use the arithmetic formula to find one function that satisfying this relation; $a_n=a+(n-1)d$. Substituting $a=1, d=1$:$$a_n=1+n.$$ May I know if there are other functions that satisfy such relation? Or there is only one function, which is $n+1$ satisfying the relation.

user26857
  • 52,094
Henry Cai
  • 633
  • How did you find that ?? –  Oct 07 '20 at 06:53
  • Are you asking how do I find f(1)=2, f(2)=3, f(3)=4? I first find that f(1) must be an even number between 1 and 6 inclusively. And then, I use prove by contradiction to show that f(1) doesn't equal to 4 and 6. – Henry Cai Oct 07 '20 at 06:56

4 Answers4

4

Induction! Suppose $f(n)=n+1$ Then, $$f(n)+2f(f(n))=3n+5$$

is equivalent to $$n+1+2f(n+1)=3n+5$$

so we get $$2f(n+1)=2(n+2)$$

So $f(n+1)=n+2$, which is what we wanted.

Moreover, as you calculated $f(1)=2$, our induction is complete. (note that this is a very important step)

  • 1
    Thank you so much, so there would be only 1 function satisfying the relation, and that is n+1? – Henry Cai Oct 07 '20 at 06:57
  • Yes, but I haven't looked myself into $f(1)=2$. If you cannot prove that, then you cannot use the induction. I am a bit skeptical. However, I repeat, if $f(1)=2$ the only function is $f(k)=k+1$ –  Oct 07 '20 at 07:00
  • What do you mean by "our induction is complete" ? –  Oct 07 '20 at 07:08
  • If you want to make an induction, there are 2 steps. First of all, state the reccursive result you want to prove, and prove it under the assumption it is true for smaller numbers (in our case, proving $f(n+1)=n+2$ given that $f(n)=n+1$) and second of all, verify the hypothesis for the first value (in our case $n=1$, i.e. $f(1)=2$). –  Oct 07 '20 at 07:10
  • @Vlad if you assume that $f(n) \in \Bbb N,$ for all $n \in \Bbb N$ then you can readily see that $f(1)$ has to be an even number between $1$ and $6$ and that leaves only $3$ possibilities for $f(1).$ Try to show that $f(1) \neq 4,6$ under the assumption. – Anacardium Oct 07 '20 at 07:27
  • If $f(1) = 4$ then $f(4) = 2$ but then $2 + 2 f(2) = 17.$ So $f(2) \notin \Bbb N.$ Similarly if $f(1) = 6$ then $f(6) = 1$ but this implies $1 + 2 f(1) = 23.$ So $f(1) = 11,$ a contradiction to the fact that $f(1) = 6.$ This proves that $f(1) = 2.$ – Anacardium Oct 07 '20 at 07:30
  • Yes, you are right, I just didn't do the calculations, I never denied it :) –  Oct 07 '20 at 07:33
3

Here is an interesting solution given by user littletush in https://artofproblemsolving.com/community/c6h446713p2514093.

If we let $g(n)=f(n)-n-1$ and substitute it to the functional equation (this is motivated by observing that $f(n)=n+1$ is at least one of solutions), we get $$3g(n)=-2g(g(n)+n+1).$$ However then we see $2\mid g(n)$ for all $n$, which in turn means $2 \mid g(g(n)+n+1)$, which in turn means $4 \mid g(n)$, and so on, we can easily prove that generic $2^k \mid g(n)$ for all $k, n$. Only integer that can satisfy this property is $0$ (remember values of $g$ can be also non-positive integers, as opposed to values of $f$), thus we have $g(n)=0$ and so $f(n)=n+1$ follows.

Sil
  • 16,612
0

Let $f(n)=an+b$, then $$f(n)+2f(f(n)=3n+5 \implies an+b+2(a(an+b)+b)=3n+5$$ $$\implies 2a^2+a=3, a+2ab+2b=5$$ $$ \implies a=1, b=1.$$ So $f(n)=n+1.$ The other solution for $a=-3/2$ gives $0=5$ which is invalid.

Z Ahmed
  • 43,235
0

Assuming a linear function $f(n)=an+b$,

$$an+b+2a^2n+2ab+2b=3n+5$$ and $$\begin{cases}a+2a^2=3,\\(3+2a)b=5\end{cases}$$

The only solution is $a=b=1$.

Of course this says nothing about possible nonlinear solutions. A polynomial cannot do.

As explained by @Vlad, we can prove by induction that $f(n)=n+1$.

Indeed,

$$f(n)=n+1\implies n+1+2f(n+1)=3n+5\implies f(n+1)=n+2$$ and $f(1)=2$ is known. So this solution is guaranteed.

  • At least, we can determine that a polynomial of degree $1$ is the only solution since $\deg(f(f)) = 2\deg(f) $ if we are seeking for only polynomials. $\ddot\smile$ – VIVID Oct 07 '20 at 07:04