$S$ is the set of functions $f:\mathbb{N} \to \mathbb{R}$ that satisfy the following conditions: I. $f(1) = 2$ II. $f(n+1) \geq f(n) \geq \frac{n}{n + 1} f(2n)$ for $n = 1, 2, \ldots$ Find the smallest $M \in \mathbb{N}$ such that for any $f \in S$ and any $n \in \mathbb{N}, f(n) < M$.
Problem
Source: China TST 1996, problem 2
Tags: function, limit, induction, strong induction, algebra unsolved, algebra
25.05.2005 20:25
I hope it's correct Because of (II) we have f ( n + 1 ) \geqslant f ( n ), thus f is increasing. But in the same time \frac{n + 1}{n} \cdot f ( n ) \geqslant f ( 2 n ) and as n \rightarrow \infty, f ( n ) \geqslant f ( 2 n ) (because f ( n )=o ( n ) and thus \lim_{n \rightarrow \infty} \frac{1}{n} f ( n ) = 0) and since for all n \in N, f ( 2 n - 1 ) \geqslant f ( n ) it follows that f ( 2 n - 1 ) \geqslant f ( n ) \geqslant f ( 2 n ) (as n \rightarrow \infty) It does mean that for all n \in N, f must be constant, thus f ( n ) = f ( 1 ) and f ( 1 ) = 2. So M = 3.
25.05.2005 20:46
That's a serious misuse of limit language- something that's eventually true doesn't have to be immediately true. $f(2)\le\frac21f(1)=4$ $f(4)\le\frac32f(2)\le6$ $f(3)\le f(4)\le6$ $f(8)\le\frac54f(4)\le7.5$ $f(5)\le f(6)\le f(7)\le f(8)\le7$ $f(16)\le\frac98f(8)\le7+\frac78$ $f(n)\le7$ for all $n$ and $f$. The example $f(1)=2,f(2)=4,f(3)=f(4)=6,f(n)=7$ for $n\ge5$ shows that this estimate is the best possible.
25.05.2005 21:03
I'll no more post when in doubt
19.06.2006 13:43
,you need to take all f into account.i think ans. is 9,there exists such function satisfying given conditions,it is 9 can be shown using strong induction or researchers paradox of polya. ,for reference see,mathematical miniatures-titu,svetoslav.
14.05.2018 04:22
Actually the answer is [9.537]+1, which is 10, according to WolframAlpha This, similar to jmerry’s idea, can be conducted from Infinity 2Product (2^n+1)/2^n n=0 But I don’t know how to use some basic knowledge and simple arithmetics to prove it
14.05.2018 04:41
Mr.Dan Li gives me an excellent solution The first two lines are for the lower bound and the last two lines are for the upper bound, which use this inequality Lnx <= x-1
Attachments:

14.05.2018 06:45
So, looking back - my argument was a solution to a slightly different problem - integer-valued functions. Without that restriction, we can indeed step up a little farther.