MathDB

Prove a function

Source: Indian IMOTC 2004 Day 3 Problem 2

September 23, 2005

functionalgebra unsolvedalgebra

Problem Statement

Define a function

g(1) = 1

by the following rule: (a)

g(n+1) = 1 + g( n +1 - g(g(n)))

is nondecrasing (b) for each

n

,

g(n)

i sthe number of times

n

appears in the range of

g

, Prove that

g(1) = 1

and

g(n+1) = 1 + g( n +1 - g(g(n)))

for all

n \in \mathbb{N}

Back to Problems View on AoPS