Я написал $$ T (n) = T (n-1) + T (n-2) + c_0 n $$, и я предполагаю, что T ( n) большой O из T (n) <= 2 ^ n + c_0 n. и доказать по индукции. </p>
Я застрял в доказательстве базового случая. Как я могу показать, что 2c1 меньше 8?
И каков общий подход, разворачивая повторение?
Спасибо!