Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site ecrcvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!ucbvax!ucdavis!lll-crg!gymble!umcp-cs!seismo!mcvax!unido!ecrcvax!david
From: david@ecrcvax.UUCP (David McKelvie)
Newsgroups: net.math
Subject: Question on recursive defnd function
Message-ID: <156@ecrcvax.UUCP>
Date: Mon, 14-Oct-85 10:19:35 EDT
Article-I.D.: ecrcvax.156
Posted: Mon Oct 14 10:19:35 1985
Date-Received: Thu, 17-Oct-85 01:45:40 EDT
Reply-To: david@ecrcvax.UUCP (David McKelvie)
Organization: ECRC, D-8000 Muenchen 81, W. Germany
Lines: 24


	*
	
	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