Problem: Let f:Z→Z be a function such that f(0)=2 and for all integers x, f(x+1)+f(x−1)=f(x)f(1). Prove that for all integers x and y, f(x+y)+f(x−y)=f(x)f(y).
Solution
Solution: Let us first prove the result for nonnegative y by strong induction on y. If y=0, (2) becomes f(x)+f(x)=f(x)f(0), which is true since f(0)=2, and if y=1, (2) is the same as (1). Let us assume (2) for y=z−1 and y=z and try to prove it for y=z+1. We have f(x+z−1)+f(x−z+1)=f(x)f(z−1)f(x+z)+f(x−z)=f(x)f(z) Multiplying (4) by f(1) and subtracting (3) yields 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) as desired. It remains to prove (2) for y<0. If y=−z and z>0, (2) becomes f(x−z)+f(x+z)=f(x)f(−z) which would follow from (2) for y=z if f(−z)=f(z). To prove this, let x=0 and y=z in (2), getting f(z)+f(−z)f(z)+f(−z)f(−z)=f(0)f(z)=2f(z)=f(z).
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.