1. OBSERVAÇÃO: Para certas relações de recorrência, pode não ser imediato
  perceber se a base da recorrência cobre todos os casos necessários.
Um exemplo é a seguinte relação de recorrência:

  t(n) = 1,                     se n = 33 ou 34;
  t(n) = t(piso(n/2) + 17) + 1, se n > 34.

Observe que não existe valor de "n" tal que t(n) esteja definido
  em termos de t(1), ou t(2), ou t(y) se y < 17.
Em tais casos, porém, pode-se apresentar uma prova explícita
  de que a função em questão está definida para todos os valores desejados,
  como exemplificado abaixo.

2. EXERCÍCIO: sendo f(n) = piso(n/2) + 17, mostre que, para todo n natural,

   a) f(n) < n <=> n > 34.
   b) f(n) = n <=> n = 33 ou 34.
   c) f(n) > n <=> n < 33.

3. LEMA: sendo f(n) = piso(n/2) + 17, a função

  t(n) = 1,           se n = 33 ou 34;
  t(n) = t(f(n)) + 1, se n > 34.

está definida para todo natural n >= 33.

===================================================
---------------------- PROVA ----------------------
Nós provaremos a afirmação

  para todo natural n, se n < 33, então t(n) não está definido, e,
  se n >= 33, então t(n) está definido.

por indução em "n":

* BASE (n = 0): a relação de recorrência não apresenta caso para n = 0,
  e portanto a função não está definida para n = 0.

* HIPÓTESE DE INDUÇÃO: o resultado vale para todo n' < n.

* PASSO (n > 0): se n < 33, pelo mesmo argumento da base,
  t não está definida para n, CQD.

  Se n = 33 ou n = 34, então, pela primeira equação da recorrência,
  a função está definida para n, e vale 1.

  Se n > 34, então, pela 2a equação da recorrência,
    t(n) é definido em função de t(f(n)); logo, se t(f(n)) estiver definido,
    então t(n) também o estará.
  De fato, pelo exercício anterior, temos f(n) < n (pois n > 34).
  Logo, aplicando a hipótese de indução, concluímos que,
    se f(n) >= 33, então t(f(n)) está definido.
  De fato, temos n > 34, e portanto f(n) = piso(n/2) + 17 >= 17 + 17 >= 33.
  Logo, t(f(n)) está definido, e portanto que t(n) também o está, CQD.

---------------------- PROVA ----------------------
===================================================

(OBSERVAÇÃO: na prova acima, nós deixamos o argumento na forma exata esperada
  para o princípio de indução, o que tem a vantagem de dar confiabilidade à prova.
Como exemplificado a seguir, porém, é possível apresentar o argumento
  de forma mais natural, incluindo na base todos os casos iniciais,
  e deixando no passo somente o caso recursivo.
De fato, uma argumentação apresentada na forma abaixo pode facilmente ser reapresentada
  na forma acima, e, por essa razão, nós tomaremos a liberdade de utilizá-la daqui para a frente.)

===============================================================
---------------------- PROVA ALTERNATIVA ----------------------
Nós provaremos a afirmação

  para todo natural n, se n < 33, então t(n) não está definido, e,
  se n >= 33, então t(n) está definido.

por indução em "n":

* BASE (n <= 34): Os casos possíveis são os seguintes:

  a) n < 33: nesse caso, t(n) obviamente não está definido, pois a recorrência
             não apresenta equação para n < 33.

  b) n = 33 ou 34: nesse caso, pela primeira equação da recorrência, t(n) está
             definido e vale 1.

* HIPÓTESE DE INDUÇÃO: o resultado vale para todo n' < n.

* PASSO (n > 34): para n > 34, pela 2a equação da recorrência,
    t(n) é definido em função de t(f(n)); logo, se t(f(n)) estiver definido,
    então t(n) também o estará.
  De fato, pelo exercício anterior, temos f(n) < n (pois n > 34).
  Logo, aplicando a hipótese de indução, concluímos que,
    se f(n) >= 33, então t(f(n)) está definido.
  De fato, temos n > 34, e portanto f(n) = piso(n/2) + 17 >= 17 + 17 >= 33.
  Logo, t(f(n)) está definido, e portanto que t(n) também o está, CQD.

---------------------- PROVA ALTERNATIVA ----------------------
===============================================================


4. LEMA: sendo f(n) = piso(n/2) + 17, a função

  t(n) = 1,           se n = 33 ou 34;
  t(n) = t(f(n)) + 1, se n > 34.

é O(n).

===============================================================
--------------------------- PROVA ---------------------------
Sejam c = 1 e n_0 = 33.

Nós provaremos que

  para todo natural n, se n >= 33, então t(n) <= c*n = n,

o que, pela escolha de c e n_0, mostra que que t = O(n), como desejado.

Por indução em n, temos:

* BASE (n <= 34): Os casos possíveis são:

  a) n < 33: nesse caso, o resultado vale por vacuidade,
             pois n não é maior ou igual a 33.

  b) n = 33 ou n = 34: temos t(n) = 1 <= n, CQD.

* HI: para todo n' < n, se n' >= 33, então t(n') <= n'.

* PASSO (n > 34): temos

  t(n) = t(piso(n/2) + 17) + 1
      <= piso(n/2) + 17 + 1     --> pela HI, pois n > 34 => piso(n/2) + 17 < n,
                                        e, além disso, n > 34 => piso(n/2) + 17 >= 33.
      <= piso(n/2) + teto(n/2)  --> pois n >= 35
       = n, CQD.

--------------------------- PROVA ---------------------------
===============================================================


5. LEMA: sendo f(n) = piso(n/2) + 17, a função

  t(n) = 1,           se n = 33 ou 34;
  t(n) = t(f(n)) + 1, se n > 34.

é O(lg n).

===============================================================
--------------------------- PROVA ---------------------------
Sejam c = máx { t(n) : 33 <= n <= 3399 }, n_0 = 33 e b = 200/101.

Nós mostraremos que, para todo n >= n_0,

  t(n) <= c * log_b(n).

Como c*log_b(n) = O(lg n), então nós teremos demonstrado o resultado desejado.

Por indução em n:

* BASE (n < 3400): para qualquer n de 33 a 3399, temos:

  t(n) <= c                --> pela definição de c
       <= c*log_b(n), CQD. --> pois log_b(n) >= 1 para todo n >= 33 > 200/101

* HIPÓTESE DE INDUÇÃO: t(n') <= c*log_b(n'), para todo n' < n.

* PASSO (n >= 3400): temos:

  t(n) = t(piso(n/2) + 17) + 1
      <= c*log_b(piso(n/2) + 17) + 1  --> pois piso(n/2) + 17 < n (pois n > 34)
      <= c*log_b(n/2 + 17) + 1
       = c*log_b((n + 34)/2) + 1
      <= c*log_b((n + n/100)/2) + 1   --> pois n >= 3400
       = c*log_b(n/(200/101)) + 1
       = c*( log_b(n) - log_b(200/101) ) + 1
       = c*( log_b(n) - 1 ) + 1       --> pois b = 200/101
       = c*log_b(n) - c + 1
      <= c*log_b(n), CQD.             --> pois c >= t(33) >= 1

--------------------------- PROVA ---------------------------
===============================================================


6. TEOREMA (MESTRE): sejam constantes reais a >= 1 e b > 1,
   f(n) uma função real e t(n) uma função definida por uma
   equação de recorrência da forma

   t(n) = a*t(n/b) + f(n),

   onde "n/b" na verdade significa ou piso(n/b) ou teto(n/b).
   Nesse caso, t pode ser limitada assintoticamente assim:

   1. Se f(n) = O(n^(log_b(a) - d)), para algum real d > 0,
      então t(n) = ϴ(n^(log_b(a))).

   2. Se f(n) = ϴ( n^(log_b(a)) * (lg n)^k ), para algum k >= 0,
      então t = ϴ( n^(log_b(a)) * (lg n)^(k+1) ).

   3. Se f(n) = Ω(n^(log_b(a) + d)), para algum real d > 0,
      e se a*f(n/b) <= c*f(n) para alguma constante c < 1 e n grande
      o suficiente, então t(n) = ϴ(f(n)).

(OBSERVAÇÃO: o caso 2 acima é uma generalização daquele que foi escrito
   em sala e que aparece na segunda edição do livro-texto da disciplina.
 Essa versão mais geral aparece no capítulo 5 deste livro
   http://ww3.algorithmdesign.net/ .
 O capítulo em questão é livremente acessível neste endereço:
   http://ww3.algorithmdesign.net/sample/ch05-patterns.pdf .)