Let Tn 3 for n 1 and for all n greaterthanorequalto 2 Tn

Let T(n) = 3 for n = 1, and for all n greaterthanorequalto 2, T(n) = T(n - 1) + 2n - 3. Solve this recurrence using the mathematical induction method, (i.e., You need to guess a solution - explicit solution of T(n) (you need to specify all coefficients, do not use 0, Ohm, or theta), and assume that the guess is true for n = k. Then prove that it is also true for n = k + 1. You also need to prove that your guess is true for the base case.

Solution

Given T(1) = 3

Now, from the given equation for n>=2

T(2) = T(1) + 2*2 - 3 = 3+4-3 = 4

T(3) = T(2) + 2*3 -4 = 4+ 6-3 = 7

Similarly, T(4) = 12, T(5) = 19, T(6) = 28, T(7) = 39, T(8) = 52, ....

This leads to a guess of T(n) = n² - 2(n-2) for n>=2

Now, we will prove that our guess is true by Mathematical Induction,

for n = 2 the guess equation will give, T(2) = 2² - 2(2-2) = 4

Thus the guess is true for n = 2.

for n = 3 the guess equation will give, T(3) = 3² - 2(3-2) = 9-2 = 7

Thus the guess is also true for n = 3.

Let our guess is true for n = k

so T(k) = k² - 2(k-2) ...(i)

Now, we will prove that our guess is true for n = k+1,

i.e. T(k+1) = (k+1)² - 2(k+1-2)

Considering RHS,

(k+1)² - 2(k+1-2) = k² + 2k +1 - 2(k -2) -2 = k² - 2(k-2) +2k -1 = T(k) + 2k -1 (from equation i) .....(ii)

Now, from the given equation i.e. T(n) = T(n-1) +2n - 3

So, T(n+1) = T(n) + 2(k+1) -1 = T(n) + 2k -1   ....(iii)

Thus from eq (ii) & eq (iii), it is clear that our guess is true for n = k+1 also.

Hence by Mathematical induction, it is proved that our guess is true.