Suppose a function f:Z+→Z+ satisfies f(f(n))+f(n+1)=n+2 for all positive integer n. Prove that f(f(n)+n)=n+1 for all positive integer n.
Problem
Source: 2012 Indonesia Round 2.5 TST 4 Problem 1
Tags: function, induction, floor function, algebra unsolved, algebra
31.05.2012 13:14
chaotic_iak wrote: Suppose a function f:Z+→Z+ satisfies f(f(n))+f(n+1)=n+2 for all positive integer n. Prove that f(f(n)+n)=n+1 for all positive integer n. 1) f(2)=2 and f(3)=2 and f(4)=3 =========================== f(2)=3−f(f(1)) and so f(2)∈{1,2} If f(2)=1, then f(3)=4−f(f(2))=4−f(1) implies f(1)∈{1,2,3} but then : f(1)=1 ⟹ 1=f(2)=3−f(f(1))=2, impossible f(1)=2 ⟹ 1=f(2)=3−f(f(1))=3−f(2)=2, impossible f(1)=3 ⟹ 1=f(2)=3−f(f(1))=3−f(3) and so f(3)=2, in contradiction with f(3)=4−f(f(2))=4−f(1)=1 So f(2)=2 f(3)=4−f(f(2))=2 f(4)=5−f(f(3))=5−f(2)=3 Q.E.D. 2) f(1)=1 and ∀n≥2 : n≥f(n)≥2 =============================== f(n+1)=n+2−f(f(n))≤n+1 and so f(n)≤n ∀n≥2 Let then n≥2 : if f(n)≥2, we get f(f(n))≤f(n)≤n and so f(n+1)=n+2−f(f(n))≥2 And since f(2)≥2, we get f(n)≥2 ∀n≥2 But 2=f(2)=3−f(f(1)) implies f(f(1))=1 and so f(1)<2 and so f(1)=1 Q.E.D. 3) ∀n≥2 f(n)∈{f(n−1),f(n−1)+1} ============================== Suppose f(k)∈{f(k−1),f(k−1)+1} ∀k∈[2,n] with n>ge2 If f(n)=f(n−1), then f(n+1)=n+2−f(f(n))=1+(n+1−f(f(n−1)))=1+f(n) If f(n)=f(n−1)+1 : since f(n−1)+1∈[2,n], we get f(f(n−1)+1)∈{f(f(n−1)),f(f(n−1))+1} and so : If f(f(n−1)+1)=f(f(n−1)) : f(n+1)=n+2−f(f(n)) =n+2−f(f(n−1)+1) =n+2−f(f(n−1)) =1+f(n) If f(f(n−1)+1)=f(f(n−1))+1 : f(n+1)=n+2−f(f(n)) =n+2−f(f(n−1)+1) =n+1−f(f(n−1)) =f(n) And so f(n+1)∈{f(n),f(n)+1} And since f(k)∈{f(k−1),f(k−1)+1} ∀k∈[2,2], the induction gives the required result. Q.E.D. 4) f(f(n)+n)=n+1 ∀n ==================== Simple induction : Property is true for n=1 : f(f(1)+1)=f(2)=2 If property is true for n, then : f(n+1)∈{f(n),f(n)+1} If f(n+1)=f(n), then : f(f(n+1)+n+1)=f(n+1)+n+2−f(f(f(n+1)+n)) =f(n+1)+n+2−f(f(f(n)+n)) =f(n+1)+n+2−f(n+1) =n+2 If f(n+1)=f(n)+1, then : f(f(n)+n+1)=f(n)+n+2−f(f(f(n)+n)) =f(n)+n+2−f(n+1)=n+1 f(f(n+1)+n+1)=f(n+1)+n+2−f(f(f(n+1)+n)) =f(n+1)+n+2−f(f(f(n)+n+1)) =f(n+1)+n+2−f(n+1)=n+2 And so f(f(n+1)+n+1)=n+2 End of induction And so f(f(n)+n)=n+1 ∀n∈Z+ Q.E.D. 5)Alternative direct [magic] path ====================== It's possible to show that there is a unique function f(x) matching all requirements and that f(x)=1+⌊2x1+√5⌋ matches all the requirements and so is this unique function. It remains then casework to show f(f(n)+n)=n+1 from the direct expression of f(x) (note : solution based on benimath's solution for a similar problem here : http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2133084#p2133084 )