Solve the following recurrence relations using the initial c

Solve the following recurrence relations using the initial condition a_n = 1.

a_n = a_n/2 + d and a_n = 2a_n/2 + d

Solution

we have the recurrence relation an=an/2+d with an=1

an=an/2+d

=1²a(n/4)=........=1^ka(1)=logn=n^log1=1

another recurrence relation an=2an/2+d with an=1

an=2²a(n/2²)=............=2^ka(1)=2^logn=n^log2