# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 17.4.2008 at 12:20, in S1, there is the following noon lecture:

# The mysterious behavior of "meta-Fibonacci" sequences

## Frank Ruskey

## University of Victoria

## Abstract

This talk is concerned with the enigmatic behavior of nested recurrence relations of the form A(n) = A(n - s - A(n - a_1 ) - ... - A(n - a_p )) + A(n - s - t - A(n - b_1 ) - ... - A(n - b_p )) where 0 \leq s, 0 \leq t, a_1 \leq ... \leq a_p, and b_1 \leq ... \leq b_p. Examples include Hofstadter's famous Q sequence (p = q = 1, s = t = 0, a1 = 1, b1 = 2; from Gödel, Escher, and Bach) and the Conolly meta-Fibonacci o recurrence A(n) = A(n - A(n - 1)) + A(n - 1 - A(n - 2)). In

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page