algorithm - 帰納法によるアルゴリズムの正しい証明

Question

私は帰納法によってアルゴリズムを証明し、それがすべての n >= 0 に対して 3 ⁿ - 2 ⁿを返すことを想定しています。これは Eiffel で書かれたアルゴリズムです。

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

私の理解では、あなたはそれを 3 つのステップで証明します。基礎ステップ、帰納的仮説、および完全性の証明。これは私が現在持っているものです。

基本：

P(0) は 0 を返し、3 ⁰ - 2 ⁰ = 0 を返します。

P(1) は 1 を返し、3 ¹ - 2 ¹ = 1 です。

誘導仮説:

P(k) が0 <= k < n に対して3 ^k - 2 ^{kを返すと仮定します。}

完全性の証明:

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 ) <-帰納的仮説に基づく

これは私が立ち往生する部分です。^{これを 3 n} - 2 ⁿのように縮小するにはどうすればよいのでしょうか。

Answer 1

  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