Maths prize 2 March 2018: recursive definition


Howard Tran made the best attempt and won the prize.

The proof by induction: the question is mis-stated a bit, since g(1)=1. The thing to be proved should be that 0 < g(n) 1.

Step 1: prove true for n=2

g(2) = 2 – g(g(1)) = 2 – g(1) = 1, and 0 < 1 < 2.

Step 2: prove – if true for n=k, or in fact if true for n=1, 2, 3, 4… k, then true for n=k+1

g(k+1) = k – g(g(k))

If the claim is true for n=k, then 0 < g(k) < k

So g(k+1) = k – g(m) for some m with 0 < m < k

If the claim is true for n=1, 2, 3, 4… k, then 0 < g(m) < k-1

So 1 < g(k+1) < k

and for sure 0 < g(k+1) < k+1

The claim is true for n=1. We have also proved that if it is true for n=1, 2, 3, 4… k, then it is also true for n=k+1. So, by induction, the claim is true for all n>1.

Calculating

g(1) = 1 – g(g(0)) = 1 – g(0) = 1
g(2) = 2 – g(g(1)) = 2 – g(1) = 1
g(3) = 3 – g(g(2)) = 3 – g(1) = 2
g(4) = 4 – g(g(3)) = 4 – g(2) = 3

and so on, or easier by spreadsheet

The tree for this table of values is in fact exactly the tree shown in the puzzle.

Down the right-hand edge of the tree you see the Fibonacci series.