I was unable to solve this during the contest.
Acc. to me , the recurrence formula should be…
Tn+2 = Tn+1.T1 + 2.Tn
and T1 = 2
and T2 = 6
I checked some solutions they use something like Fibonacci Logn method to generate the answer but I don’t get it . Please help and how can I solve these type of questions in Logn when I have recurrence formula.
The Linear recurrence relation formed is a(n) = 2a(n-1)+2a(n-2) which is as good as -
2*(a(n-1)+a(n-2)).
The above equation is for 2*(Fibonacci sequence).
And for calculating nth fibonacci number efficiently -
For proof of nth fibonacci number using matrix exponentiation -
And finally here you go by just replacing 2 (where to replace is left for readers 
) in the matrix for getting your nth modified fibonacci sequence.
I drive This recurrence too, but took me to try different cases to figure it out.
How do you drive this recurrence?
what is the intution behind it?
I also went through different values for n and found the recurrence relation.
But , for a good explanation -
https://www.slader.com/discussion/question/a-horizontal-stripe-is-to-be-tiled-the-tiles-come-in-two-shapes-1-x-1-rectangles-and-1-x-2-rectangle/
You have tiles of length 1 and 2 only of colours Blue AND RED
To fill length n from (n-1) length there are two ways Blue and Red tiles of length 1
To fill length n from (n-2) length there are two ways Blue and Red tiles of length 2
nice thanks ,it has good explanation
Ohhh…great I didn’t put the value of T1 in the relation, everything was in front of me.
Thank you for the explanation bro
I still did not get why everyone creates the initial matrix of [[2, 2],[1, 0]] but not of [[2, 1],[1, 0]] ?
@chaudhary_19 Go through this blog and comment section down there:-
https://codeforces.com/blog/entry/14516
In Fibonacci , we use [[1, 1],[1, 0]] but here everyone uses [[2, 2], [1, 0]]
I want to know why? can you please explain that part
Refer to this