MathDB

Iterated functional equation with divisibility condition

Source: 2018 China TST 2 Day 2 Q3

January 9, 2018

functionDivisibilityIterationalgebrafunctional equation

Problem Statement

Let

M,a,b,r

be non-negative integers with

a,r\ge 2

, and suppose there exists a function

f:\mathbb{Z}\rightarrow\mathbb{Z}

satisfying the following conditions: (1) For all

n\in \mathbb{Z}

f^{(r)}(n)=an+b

where

f^{(r)}

denotes the composition of

r

copies of

f

(2) For all

n\ge M

f(n)\ge 0

(3) For all

n>m>M

n-m|f(n)-f(m)

Show that

a

is a perfect

r

-th power.