Computing functions

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Computing functions

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15 posts

#1 h May 21, 2025, 10:06 AM

Y by

Let $f : [0, \infty) \to [0, \infty)$ , $f(x) = \dfrac{ax + b}{cx + d}$ , with $a, d \in (0, \infty)$ , $b, c \in [0, \infty)$ . Prove that there exists $n \in \mathbb{N}^*$ such that for every $x \geq 0$
$f_n(x) = \frac{x}{1 + nx}, \quad \text{if and only if } f(x) = \frac{x}{1 + x}, \quad \forall x \geq 0.$ (For $n \in \mathbb{N}^*$ and $x \geq 0$ , the notation $f_n(x)$ represents $\underbrace{(f \circ f \circ \dots \circ f)}_{n \text{ times}}(x)$ . )

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10774 posts

#2 h May 22, 2025, 1:47 PM

Y by

Write $A:=\begin{pmatrix} a&b\\c&d\end{pmatrix},B:=\begin{pmatrix} 1&0\\1&1\end{pmatrix}$ and suppose that $A^n=kB^n$ where $k$ is some constant and where $n>1$ is a fixed positive integer. We want to show that $A=tB$ for some $t$ . Since $A^n$ has a positive entry at position $(1,1)$ , we have $k>0$ and normalising by a positive factor we assume $A^n=B^n$ .
The char equation for $A$ reads $(t-a)(t-d)=bc\iff t^2-(a+d)t+(ad-bc)=0$ with $D=(a+d)^2-4(ad-bc)=(a-d)^2+4bc\ge 0$ . Hence $A$ has real eigenvalues $\lambda,\mu$ and $\{\lambda^n,\mu^n\}=\{1,1\}$ as a multiset, since $B^n$ has a multiple eigenvalue 1. Hence $|\lambda|=|\mu|=1$ and since $\lambda+\mu={\rm Tr}(A)=a+d>0$ we have $\lambda=\mu=1$ . Hence $A^2=2A-I, B^2=2B-I$ .
Then $kA+lI=A^n=B^n=kB+lI$ where $k,l$ are constants depending on $n$ . Hence $k(A-B)=0$ and note that $k\not=0$ . Either by direct computation or by noting that $B^n$ is not a multiple of $I$ .
Hence $A=B$ .

@below: it is standard procedure to represent $f(x)={{ax+b}\over {cx+d}}$ by the matrix $A:=\begin{pmatrix} a&b\\c&d\end{pmatrix}$ . A real number $x$ is represented by the vector ${x\choose 1}$ , the point at $\infty$ is represented by ${1\choose 0}$ and we have $f(x)=Ax$ on the projective line. Indeed $f(\infty)=a/c$ . Then $f^n$ is represented by $A^n$ and we do this because it is easier to multiply matrices than to calculate the composition $f_n:=f\circ \cdots \circ f$ directly. But we have to note that matrices that are multiples of eachother describe the same linear fractional transformation.
But to answer your question: the motivation is that I have seen method before and it works.

This post has been edited 1 time. Last edited by alexheinis, May 22, 2025, 6:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

200 posts

#3 h May 22, 2025, 5:44 PM

Y by

alexheinis wrote:

Write $A:=\begin{pmatrix} a&b\\c&d\end{pmatrix},B:=\begin{pmatrix} 1&0\\1&1\end{pmatrix}$ and suppose that $A^n=kB^n$ where $k$ is some constant and where $n>1$ is a fixed positive integer. We want to show that $A=tB$ for some $t$ . Since $A^n$ has a positive entry at position $(1,1)$ , we have $k>0$ and normalising by a positive factor we assume $A^n=B^n$ .
The char equation for $A$ reads $(t-a)(t-d)=bc\iff t^2-(a+d)t+(ad-bc)=0$ with $D=(a+d)^2-4(ad-bc)=(a-d)^2+4bc\ge 0$ . Hence $A$ has real eigenvalues $\lambda,\mu$ and $\{\lambda^n,\mu^n\}=\{1,1\}$ as a multiset, since $B^n$ has a multiple eigenvalue 1. Hence $|\lambda|=|\mu|=1$ and since $\lambda+\mu={\rm Tr}(A)=a+d>0$ we have $\lambda=\mu=1$ . Hence $A^2=2A-I, B^2=2B-I$ .
Then $kA+lI=A^n=B^n=kB+lI$ where $k,l$ are constants depending on $n$ . Hence $k(A-B)=0$ and note that $k\not=0$ . Either by direct computation or by noting that $B^n$ is not a multiple of $I$ .
Hence $A=B$ .

Sir, can you pls explain what was the motivation behind your solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

27 posts

wh0nix

#4 h May 24, 2025, 10:02 AM • 1 Y

Y by youochange

Hint

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a