MathDB

Let

a, b, c

be positive real numbers and let

[x]

denote the greatest integer that does not exceed the real number

x

. Suppose that

f

is a function defined on the set of non-negative integers

n

and taking real values such that

f(0) = 0

and

f(n) \leq an + f([bn]) + f([cn]), \qquad \text{ for all } n \geq 1.

Prove that if

b + c < 1

, there is a real number

k

such that

f(n) \leq kn \qquad \text{ for all } n \qquad (1)

while if

b + c = 1

, there is a real number

K

such that

f(n) \leq K n \log_2 n

for all

n \geq 2

. Show that if

b + c = 1

, there may not be a real number

k

that satisfies

(1).

32