# solving recurrence relation by substitution method and find asymptotic bound

Solve the following recurrence relations and give a bound for each of them.

1. $T(n)= 2T(n-3)+1$

2. $T(n) = 5T(n-4)+n$

-

a) Searched for good substitution (which gives recurrence $W_n=2W_{n-3}$) in form $T_n=W_n+a$ and got $T_n=W_n-1$.
b) Searched for good substitution (which gives recurrence $W_n=5W_{n-4}$) in form $T_n=W_n+an+b$ and got $T_n=W_n-\frac{n}{4}-\frac{5}{4}$.