通过归纳证明算法正确

Question

我应该通过归纳法证明一个算法，并且它对所有 n>= 0 返回 3 n - 2ⁿ。这是用埃菲尔铁塔编写的算法。

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

我的理解是，你分三步证明。基步、归纳假设和完备性证明。这是我目前拥有的。

基础：

P（0） 返回 0,3 0 - 2 0 =⁰。

P（1） 返回 1,3 1^- 2 1 =¹。

归纳假设：

假设 P（k） 返回 3 k - 2 k 表示 0 <=^k <n。>

完整性证明：

对于 n，P（n） 返回 5（P（n-1）） - 6（P（n-2））

5（P（n-1）） - 6（P（n-2））

5（3^n-1 - 2^n-1） - 6（3 n-2 - 2^n-2） <<sup>- 基于归纳假设

这是我卡住的部分。我到底应该如何将其减少到 3 n - 2ⁿ？

Answer 1

使用 3 n-1 = 3.3 n-2

和 2 n-1 = 2.2^n-2 的事实：

5（3^n-1 - 2 n-1） - 6（3^{n-2 - 2 n-2}）

= 15（3 n-2） - 10（2 n-2） - 6（3 n-2）

+ 6（2^n-2）

= 9.3 n-2 - 4.2^n-2

= 3 n - 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