@shesh_neo : You have to form a recurrence relation and solve it and apply initial conditions to get to the closed form . Let me know if you have trouble forming a recurrence relation , I will post the relation .
for the part 1:
let’s say we have f(n) for n, so we can easily deduce, f(n+1)=f(n)*3+2^n-1
so, f(n+1)+2^(n+1)-1/2=(f(n)+2^n-1/2)*3
let’s say k(n)=f(n)+2^n-1/2
so k(1)=3/2, k(n+1)=k(n)*3, so k(n)=3^n/2
so, f(n)=3^n/2-2^n+1/2
To all the people trying this question, here’s a special note:
Don’t calculate like, a=4^n%MOD, b= 2^n%MOD and c=3^n%MOD, and then do 2*a + b/2 + b + ((c+1)/2), and similar things for R1… This will give you a wrong answer…because what we actually want to find is like : ((3^n + 1)/2)%MOD, which is Actually : (3^n + 1)%MOD * (2^MOD-2)%MOD… So don’t forget to leave the divider alone, take that into consideration too…I did this mistake many a times before realizing it !
Cheers !
@sparshgunner12 : check my solution for the recursive relation and the explanation about how to come up with the formula. Everything is mentioned in the comments.
@shesh_neo : check my solution for the recursive relation and the explanation about how to come up with the formula. Everything is mentioned in the comments.