Silly Recurrence

klostermeyer_at_hotmail.com
Date: 12/20/04 

Date: 19 Dec 2004 19:35:54 -0800

While teaching Algorithms this past term, the question
of bounds/solutions to the following recurrences came up:

T(n) = T(n-1) + T(n/2) + 1

and

T(n) = T(n-1) + T(n/2) + n

(you can assume T(1) = c for some constant c).

I played around with these, cranked out
some terms, and looked for anything similar in
some books (e.g., Sedgewick and
Flajolet) and asked a colleague with a bit more
expertise than I who said these would be hard to handle.

These are of no importance other than satisfying my
curiousity, but any techniques or good bounds would
be fun. My hunch is that at the very least the second
can't be bounded by any polynomial.

Thanks and apologies if this is a dumb question,
Chip Klostermeyer
Professor, CIS
University of North Florida