david@ecrcvax.UUCP (David McKelvie) (10/14/85)
* A while ago there was a letter in this newsletter about the following function ( first mentioned, as far as I know, in the book 'Godel,Escher,Bach'):- f(0) = 1 f(1) = 1 f(n) = f( n - f(n-1) ) + f( n - f(n-2) ) for all n >= 2 I may be missing something obvious, but has anyone or can anyone prove that these equations define a well-defined function N --> N ? I.e. f(n) <= n + 1 for all n >= 0 so that the inner terms in the third equation are >= 0 . Obviously some sort of induction is needed, but finding the correct inductive hypothesis seems difficult. -- David Mckelvie ECRC UUCP: mcvax!unido!ecrcvax!david Arabellastr. 17 UUCP Domain: david@ecrcvax.UUCP 8000 Muenchen 81, West Germany CSNET: ecrcvax!david@Germany.CSNET