MathDB
Number of integers with F(4n) = F(3n) is F(2^{m+1})

Source: IMO Shortlist 2000, A4

August 10, 2008
functionalgebrafunctional equationIMO Shortlist

Problem Statement

The function F F is defined on the set of nonnegative integers and takes nonnegative integer values satisfying the following conditions: for every n≥0, n \geq 0, (i) F(4n) \equal{} F(2n) \plus{} F(n), (ii) F(4n \plus{} 2) \equal{} F(4n) \plus{} 1, (iii) F(2n \plus{} 1) \equal{} F(2n) \plus{} 1. Prove that for each positive integer m, m, the number of integers n n with 0≤n<2m 0 \leq n < 2^m and F(4n) \equal{} F(3n) is F(2^{m \plus{} 1}).
Back to ProblemsView on AoPS