Functional Equation (Canada 1969)

For students of class 11-12 (age 16+)
mutasimmim
Posts: 107
Joined: Sun Dec 12, 2010 10:46 am

Functional Equation (Canada 1969)

Unread post by mutasimmim » Sat Sep 20, 2014 8:46 pm

Find all functions $f:N \rightarrow N$ such that $f(2)=2$ and for any two $m,n ; f(mn)=f(m)f(n)$ and $f(n+1)>f(n)$.

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Functional Equation (Canada 1969)

Unread post by *Mahi* » Sat Sep 20, 2014 9:41 pm

Hint:
The set $S_n = \{n^q | q \in \mathbb Q\}$ is dense $\forall n \in \mathbb N, n > 1$.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

mutasimmim
Posts: 107
Joined: Sun Dec 12, 2010 10:46 am

Re: Functional Equation (Canada 1969)

Unread post by mutasimmim » Sat Sep 20, 2014 9:52 pm

Hints for two different solutions:
1. Induction
or, 2. Think about the numbers $f(2^k+1),f(2^k+2),....,f(2^{k+1})$

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: Functional Equation (Canada 1969)

Unread post by Nirjhor » Sat Sep 20, 2014 10:48 pm

See that \((m,n)=(2,1)\) gives \(f(1)=1\) and \((m,n)=(2,2)\) gives \(f(4)=4\). Now \[2=f(2)<f(3)<f(4)=4\] so \(f(3)=3\). Suppose \(f(n)=n\) for \(n\le 2k\). Then \[f(2k+2)=f\left(2(k+1)\right)=f(2)f(k+1)=2k+2.\] And so \[2k=f(2k)<f(2k+1)<f(2k+2)=2k+2\] hence \(f(2k+1)=2k+1\). Therefore \(\boxed{f(n)=n}\) for all \(n\in\mathbb{N}\) by strong induction.
Last edited by Nirjhor on Sun Sep 21, 2014 10:34 pm, edited 1 time in total.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Functional Equation (Canada 1969)

Unread post by *Mahi* » Sat Sep 20, 2014 11:08 pm

Nirjhor wrote:The given is Cauchy's Functional Equation. Hence \(f(x)=x^n\) for any fixed \(n\in\mathbb{N}\). Now \(f(2)=2^n=2\) gives \(n=1\) so \(f(n)=n\).
Wrong. For example the following set of functions defines a solution to $f(mn) = f(m)f(n), f: \mathbb N \mapsto \mathbb N$.
\[f(\prod p_i ^{e_i}) = \prod f(p_i)^{e_i}\]
\[f(p_i) = F(p_i)\]
Where the function $F: \mathbb P \mapsto \mathbb P$ is injective.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: Functional Equation (Canada 1969)

Unread post by Nirjhor » Sat Sep 20, 2014 11:45 pm

*Mahi* wrote:
Nirjhor wrote:The given is Cauchy's Functional Equation. Hence \(f(x)=x^n\) for any fixed \(n\in\mathbb{N}\). Now \(f(2)=2^n=2\) gives \(n=1\) so \(f(n)=n\).
Wrong. For example the following set of functions defines a solution to $f(mn) = f(m)f(n), f: \mathbb N \mapsto \mathbb N$.
\[f(\prod p_i ^{e_i}) = \prod f(p_i)^{e_i}\]
\[f(p_i) = F(p_i)\]
Where the function $F: \mathbb P \mapsto \mathbb P$ is injective.
Didn't understand what you wanted to say. The equality \[f\left(\prod p_i^{e_1}\right)=\prod f\left(p_i\right)^{e_i}\] is obvious from the given multiplicativity condition. If you're saying \(F:\mathbb{P}\mapsto\mathbb{P}\) is an arbitrary injective function, how does that satisfy the conditions given?

(I've edited my comment and added an inductive solution)
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Functional Equation (Canada 1969)

Unread post by *Mahi* » Sun Sep 21, 2014 2:26 pm

For example, $F(2)=3, F(3)=2$, and $F(p)=p$ for all other prime $p$ yields a solution.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: Functional Equation (Canada 1969)

Unread post by Nirjhor » Sun Sep 21, 2014 3:13 pm

I was considering the constraint that \(f\) is strictly increasing.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Functional Equation (Canada 1969)

Unread post by *Mahi* » Sun Sep 21, 2014 10:15 pm

And I meant the part "$f:\mathbb N \mapsto \mathbb N, f(mn)=f(m)f(n) \Rightarrow$ Cauchy" is wrong, and provided a counter example. Even if you add the strictly increasing part, you'd have to prove it differently (like you did in the edit).
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: Functional Equation (Canada 1969)

Unread post by Nirjhor » Sun Sep 21, 2014 10:36 pm

Got it. So is there any other solution to the given problem?
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

Post Reply