Maths Olympiad Prep

Library / /3 of 13

Algebra Difficulty 4.8 AIME Prove it United States

Problem:
Let f:ZZf: \mathbb{Z} \rightarrow \mathbb{Z} be a function such that f(0)=2f(0)=2 and for all integers xx,
f(x+1)+f(x1)=f(x)f(1). f(x+1)+f(x-1)=f(x) f(1) .
Prove that for all integers xx and yy,
f(x+y)+f(xy)=f(x)f(y). f(x+y)+f(x-y)=f(x) f(y) .

Solution

Solution:
Let us first prove the result for nonnegative yy by strong induction on yy. If y=0y=0, (2) becomes
f(x)+f(x)=f(x)f(0), f(x)+f(x)=f(x) f(0),
which is true since f(0)=2f(0)=2, and if y=1y=1, (2) is the same as (1). Let us assume (2) for y=z1y=z-1 and y=zy=z and try to prove it for y=z+1y=z+1. We have
f(x+z1)+f(xz+1)=f(x)f(z1)f(x+z)+f(xz)=f(x)f(z) \begin{gathered} f(x+z-1)+f(x-z+1)=f(x) f(z-1) \\ f(x+z)+f(x-z)=f(x) f(z) \end{gathered}
Multiplying (4) by f(1)f(1) and subtracting (3) yields
f(x+z)f(1)f(x+z1)+f(xz)f(1)f(xz+1)=f(x)[f(z)f(1)f(z1)]f(x+z+1)+f(xz1)=f(x)f(z+1) \begin{gathered} f(x+z) f(1)-f(x+z-1)+f(x-z) f(1)-f(x-z+1)=f(x)[f(z) f(1)-f(z-1)] \\ f(x+z+1)+f(x-z-1)=f(x) f(z+1) \end{gathered}
as desired.
It remains to prove (2) for y<0y<0. If y=zy=-z and z>0z>0, (2) becomes
f(xz)+f(x+z)=f(x)f(z) f(x-z)+f(x+z)=f(x) f(-z)
which would follow from (2) for y=zy=z if f(z)=f(z)f(-z)=f(z). To prove this, let x=0x=0 and y=zy=z in (2), getting
f(z)+f(z)=f(0)f(z)f(z)+f(z)=2f(z)f(z)=f(z). \begin{aligned} f(z)+f(-z) & =f(0) f(z) \\ f(z)+f(-z) & =2 f(z) \\ f(-z) & =f(z) . \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.