Question

6. Consider the recurrence relation T(n) = 2T(n-1) + 5 for integers n 1 and T(O) = 0. Find a closed-form solution Using induction, prove your solution correct for all integers n 20.

Answer 1

TCnJ = QT(n-1) + 5 TCO)=0 put n=1, ISO TCI) = QTCHI T5 TC) = 2x0+5 = 5 TC) = 58 5x1=562'-1) TCQ) = 2x 5 + 5 = 15 = 5c23-1) T (3) = 2x15+5=35= 5CP31) not an TD = 2 x 35+5= 75 = 5(84-1) Ten) = 5Can-10 | So, the clased formed solution ITCAD = 5CQn-1)

S Tch- QT Cn Urs By Mathematic induction i felli for n=1 TEN) = 5 and Ten) = 5 cenu = 5(all so this is true for n=1. w I asume ut un hold true for k TCK) = 5(2k-1) STEP38 SHow it is true for n=k+1) TCK+1) = QTCK) + S TCK+1)=2(5 (2k-1)] + 5 TCKH) = 2045 - 010+5 TCKH) = x Kt, 5-5 | TCKH) = 5(QK+1-1) So I By induction it is true for não