Большой вопрос O - алгоритмический анализ III

У меня следующий вопрос:

Решите рекуррентное соотношение, упрощающее ответ, используя Big Обозначение "O":

f(0) = 2
f(n) = 6f(n-1)-5, n>0

Я знаю, что это неоднородное рекуррентное отношение первого порядка, и я попытался ответить на этот вопрос, но, похоже, я не могу получить правильный результат для базового случая (f (0) = 2).

Вопрос ДОЛЖЕН использовать сумму геометрических рядов форумла в рамках доказательства.

Вот мой ответ - Сумма заметок (x = y, z) - это замена прописной сигма-записи, где x - нижняя граница суммирования, инициализированного значением y, а z - верхняя граница суммирования:

1.  *change forumla:*
2.     f(n) = 6^n.g(n)
3.  => 6^n.g(n) = 6.6^(n-1) .g(n-1) -5   
4.  => g(n) = g(n-1)-5/6^n
5.  => g(n) = sum(i=1, n)-5/6^i
6.  => f(n) = 6^n.sum(i=1, n)-5/6^i
7.  => *Evaluate the sum using geometric series forumla*
8.  => sum(i = 1, n)-5/6^i = [sum(i = 1, n)a^i] -------> (a = -5/6)
9.  => *sub a = -5/6 into geometric forumla [a(1-a^n)/(1-a)]*
10. => [(-5/6(1 - (-5/6)^n))/(1-(-5/6))]
11. => g(n) = [(-5/6(1 + (5/6)^n))/(1+5/6)]
12. => f(n) = 6^n . g(n) = 6^n[(-5/6(1 + (5/6)^n))/(1+5/6)]
13. => *sub in n = 0 to see if f(0) = 2*

Во-первых, я уверен, что уравнение в строке 11 можно дополнительно упростить, а во-вторых, подстановка в n = 0 должна дать 2 в качестве результата. Я не могу получить этот ответ, когда дохожу до строки 13 ...

РЕДАКТИРОВАТЬ: Мне нужно знать, почему я не получаю f (0) = 2 при добавлении n = 0 в уравнение в строке 12. Я также хотел бы знать, как я могу упростить уравнение для f (n) в строке 12?

Кто угодно ...?

6
задан user559142 12 April 2011 в 20:00
поделиться