Re: HSC 2016 4U Marathon
Find all functions f:N->N such that f(n)+f(f(n))=2n.
(N is the set of positive integers).
You might find induction useful to justify your answer.
Since f(n) is a natural valued function, we know f(n) is natural for all n in N
f(1) + f(f(1)) = 2
The left hand side consists of two naturals. The right hand side is 2. The only way to express 2 as a sum of 2 naturals is 1 + 1. Therefore, f(1) = f(f(1)) = 1.
f(2) + f(f(2)) = 4
If f(2) = 3 then we have f(3) = 1
But then that would mean f(3) + f(f(3)) = 1 + 1 = 2 =\= 6.
Contradiction. Thus, f(2) =\= 3
If f(2) = 1, then f(f(2)) = 3 <=> f(1) = 3.
Contradiction. Thus, f(2) = f(f(2)) = 2.
P(n): f(n) = n for all n in N
P(1), P(2) are the available true base cases.
Suppose P(k) is true for all 0 < k < n + 1, and that P(n + 1) is not true.
Assumed: f(1) = 1, ... f(n) = n, f(n + 1) =\= n + 1
f(n+1) + f(f(n + 1)) = 2n + 2
Suppose f(n + 1) = m where m < n + 1
But then f(n) + f(f(n) = m + f(m) = 2m < 2n + 2
Thus, f(n + 1) cannot be less than n + 1
Suppose f(n+1) = m where m > n + 1
Then f(n + 1) + f(f(n+1)) = m + f(m) = 2n + 2
Then f(m) = 2n + 2 - m < n + 1 since m > n + 1
Let 2n + 2 - m = m* < n+1
But then f(m) + f(f(m)) = m* + m* = 2m* < 2n + 2 < 2m
Which is a contradiction. Thus, f(n+1) cannot be greater than n+1
So now we have n < f(n+1) < n+2
f(n+1) is an integer. Thus, f(n+1) can only be equal to n+1, since the inequality is necessarily true.
So if P(1), ..., P(n) is true, then P(n+1) cannot be untrue, i.e. it must also be true.
By the Axiom of Mathematical Induction, P(n) is true for all n in N.
So the only solution to the functional equation is f(n) = n.
■