Доказывая алгоритм правильно по индукции

Question

Я должен доказать, алгоритм по индукции, и что она возвращает 3 ^п - 2 ^п для всех п> = 0. Это алгоритм, написанный на Eiffel.

P(n:INTEGER):INTEGER; 
    do 
    if n <= 1 then 
     Result := n 
    else 
     Result := 5*P(n-1) - 6*P(n-2) 
    end 
    end 

Я понимаю, что вы доказываете это в три этапа. Базисный шаг, индуктивная гипотеза и доказательство полноты. Это то, что у меня есть сейчас.

Основа:

Р (0) возвращает 0 и 3 - 2 = 0.

Р (1) возвращает 1 и 3 - 2 = 1.

Индуктивный Гипотеза:

Предположим, что P (k) возвращается 3 ^k - 2 ^k за 0 < = k < n.

Доказательство полноты:

Для п, Р (п) возвращает 5 (Р (п-1)) - 6 (P (N-2))

5 (P (N -1)) - 6 (Р (п-2))

5 (3 ^п-1 - 2 ^п-1) - 6 (3 ^п-2 - 2 ^п-2) < - Основываясь на индуктивной гипотезе

Это та часть, где я застреваю. Как, черт возьми, я должен уменьшить это, чтобы выглядеть как 3 ⁿ - 2 ⁿ?

Answer 1

Используйте тот факт, что 3 ^п-1 = 3.3 ^п-2 и 2 ^п-1 = 2,2 ^п-2:

5 (3 ^п-1 - 2 ^п-1) - 6 (3 ^п-2 - 2 ^п-2)

= 15 (3 ^п-2) - 10 (2 ^п-2) - 6 (3 ^п-2) + 6 (2 ^п-2)

= 9,3 ^п-2 - 4.2 ^п-2

= 3 ^п - 2 ^п

Answer 2

5(3^(n-1)-2^(n-1))-6(3^(n-2)-2^(n-2)) = 
= 5*3^(n-1)-5*2^(n-1)-6*3^(n-2)+6*2^(n-2) = 
= 5*3^(n-1)-5*2^(n-1)-2*3^(n-1)+3*2^(n-1) = 
    --------- ========= --------- ========= 
= 3*3^(n-1)-2*2^(n-1) = 
= 3^n - 2^n