Problem:
The function f is defined on the set of integers and satisfies
f(n)={n−3,f(f(n+5)),​ if n≥1000 if n<1000​
Find f(84).
Solution:
Rather than assaulting f(84) directly, it is advantageous to start with values of f(n) near n=1000, and search for a pattern when n is less than 1000, thereby utilizing the recursive definition of f.
Indeed, one finds that
f(999)f(998)f(997)f(996)f(995)​=f(f(1004))=f(1001)=998,=f(f(1003))=f(1000)=997,=f(f(1002))=f(999)=998,=f(f(1001))=f(998)=997,=f(f(1000))=f(997)=998,​(1)
on the basis of which one may conjecture that
f(n)={997, if n is even and n<1000,998, if n is odd and n<1000.​(2)
To prove (2), it is convenient to use downward induction. In this, the inductive step is to prove (2) for n, assuming that it is true for al1 m,n<m<1000. Since the definition relates f(n) to f(n+5), we can do the inductive step only when n+5<1000, that is, we must verify the truth of (2) for n=999,998,…,995 separately. This was done in (1). Now for n<995,
f(n)=f(f(n+5))={f(997)=998, if n+5 is even ,f(998)=997, if n+5 is odd .​
Noting that n is even when n+5 is odd, and that n is odd when n+5 is even, completes the proof. In particular, it follows from (2) that f(84)=997​.
The problems on this page are the property of the MAA's American Mathematics Competitions