MathDB

1

Part of 1990 IberoAmerican

Problems(1)

Integer function and powers of two

Source: Iberoamerican Olympiad 1990, Problem 1

5/21/2007
Let ff be a function defined for the non-negative integers, such that: a) f(n)=0f(n)=0 if n=2j−1n=2^{j}-1 for some j≥0j \geq 0. b) f(n+1)=f(n)−1f(n+1)=f(n)-1 otherwise. i) Show that for every n≥0n \geq 0 there exists k≥0k \geq 0 such that f(n)+n=2k−1f(n)+n=2^{k}-1. ii) Find f(21990)f(2^{1990}).
functioninduction