Proving an algorithm correct by induction

Question

I am supposed to prove an algorithm by induction and that it returns 3ⁿ - 2ⁿ for all n >= 0. This is the algorithm written in Eiffel.

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

My understanding is that you prove it in three steps. Basis step, Inductive Hypothesis, and Proof of completeness. This is what I have currently.

Basis:

P(0) returns 0, and 3⁰ - 2⁰ = 0.

P(1) returns 1, and 3¹ - 2¹ = 1.

Inductive Hypothesis:

Assume P(k) returns 3^k - 2^k for 0 <= k < n.

Proof of completeness:

For n, P(n) returns 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) <- Based on inductive hypothesis

This is the part where I get stuck. How the hell am I supposed to reduce this to look like 3ⁿ - 2ⁿ?

Answer 1

Use the fact that 3^n-1 = 3.3^n-2 and 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ⁿ - 2ⁿ