Substitution Proof

powered by FreeFind

Modified: 

Use backward substitution to find then prove the closed-end equation for:

T(1) = 1              

T(n) = T(n-1) + 5  for n>1

By backward substitution the recurrence yields:

T(n) = T(n-1) + 5 = T(n-2)+5 + 5 sub. T(n-1) = T(n-2)+5
  = T(n-2)+2*5 = T(n-3)+5 + 2*5 sub. T(n-2) = T(n-3)+5
  = T(n-3)+3*5 = T(n-3)+5 + 3*5 sub. T(n-3) = T(n-4)+5
  = T(n-4)+4*5    

Substituting i times yields (we're in luck, no summation!):

T(n)= T(n-i) + i*5

Closed-end

Base:  T(1) = T(n-i)

n-i = 1 or i=n-1

T(1) = T(1-i) = T(1-(n-1)) = T(1-(1-1)) = T(1)

Closed-end solution by substitution:

T(n) = T(n-i) + i*5
  = T(n-(n-1)) + (n-1)*5
  = T(1) + (n-1)*5
  = 1 + (n-1)*5
  = 5n-4

Proof: T(n) = 5n-4

T(1) = 1

T(n) = T(n-i) + 5 for n>1

Base:

T(1) = 5n-4 = 1*5-4 = 1

Assumption:

T(n) = 5n-4

Show:

T(n+1) = 5(n+1) - 4

T(n+1) = T(n+1-1) + 5
  = T(n) + 5
  = 5n-4+5
  = 5(n+1) - 4