EASY
Part 1 closed form: (3^n+1)/2 - 2^n
Part 2 closed form: 2*4^(n-1) - 3^n + 2^(n-1) + 2^n - (3^n+1)/2
The answer (for both 1 and 2) is in the form of a * 4^n + b * 3^n + c * 2^n + d for some small constants a,b,c,d.
You can calculate 4^n%MOD, 3^n%MOD, 2^n%MOD in log(n) time using fast exponentiation for an overall complexity of O(log(n)).
Can be found here.
Can be found here.
anyone pls explain how the closed form arrived
@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 .
please post the recursive relation and how to come up with the formula.
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
@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.
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 ! 
I get a different closed form, maybe we have some different detail 
mine is