Substitution Proof

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-1) + 5 for n>1

Base:

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

Assumption:

T(n) = T(n-1) + 5  = 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