Proving an algorithm correct by induction

0
votes

I am supposed to prove an algorithm by induction and that it returns 3n - 2n 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 30 - 20 = 0.

P(1) returns 1, and 31 - 21 = 1.

Inductive Hypothesis:

Assume P(k) returns 3k - 2k 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(3n-1 - 2n-1) - 6(3n-2 - 2n-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 3n - 2n?

2
algorithmcorrectnessinductioneiffelproof-of-correctness
Not to put too fine a point on it, but algebra should work. – U2EF1
Now for the followup question: how do you figure out it's 3^n - 2^n in the first place? – IVlad
@IVlad it was given. – user3325783
@Jimenemex: in your program, you wrote 5*g(n-1) - 6*g(n-2)? What is g? – Grégoire C
@geceo indeed. My mistake. should be P(n) – user3325783

2 Answers

2
votes

Use the fact that 3n-1 = 3.3n-2 and 2n-1 = 2.2n-2 :

5(3n-1 - 2n-1) - 6(3n-2 - 2n-2)

= 15(3n-2) - 10(2n-2) - 6(3n-2) + 6(2n-2)

= 9.3n-2 - 4.2n-2

= 3n - 2n

1
votes
  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