6.1.Task: Solve the following recurrence relations by using the following methods. 1.Backward Substitution Method 2.Forward Substitution Method 3.Recursion Tree Method 4.Telescoping Method 

i.X(n) = X(n ‒ 1) + 5 for n > 1, X(1) = 0

ii.X(n) = 3X(n ‒ 1) for n > 1, X(1) = 4

iii.X(n) = X(n ‒ 1) + n for n > 0, X(0) = 0 iv.X(n) = X( ) + n for n > 1, X(1) = 1 (solve for n=2k) 

v.X(n) = X( ) + n for n > 1, X(1) = 1 (solve for n=3k) 

vi.X(n) = X(n-1) + X(n-2) + 1 for n > 1, X(0)=0, X(1)=1 

vii.X(n) = 5X( ) + C for n > 1,X(1) = 1 

viii.X(n) = 5X( ) + n for n > 1,X(1) = 1

 ix.X(n) = 2( X( ) + n ) for n > 1,X(1) = 1 x.X(n) = X( ) + X( )+ n2 for n > 1,X(1) = 1