# Can anybody help in finding Matrix Exponentiation in this Recurrence Relation

Problem Here

Actually recurrence relation is dp[n][0]= dp[n-1][0]+dp[n-1][1]
dp[n][1]=dp[n-1][0]

Here 0 denotes doesnt go while 1 denotes had gone to workout and n denotes day

now how to use matrix exponentiation in this

1 Like

Iâ€™ve explained them here.

1 Like

You are thinking more than needed.

If you check the answers for different N, you will get a sequence as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \cdots for 0 <= N <= 10^{18}.

Well, now you familiar with this sequence I think. Ring a Bell, itâ€™s a Fibonacci Sequence.
There are tons of articles out there to solve this problem which boils down to calculate the N^{th} term of the Fibonacci Sequence.

Recently @anon79763389 has posted a nice article related to different methods of calculating the Nth term of the Fibonacci Sequence.
You can refer to the article here: https://procoderforu.com/fibonacci-sequence/

2 Likes

Thanks Very will explained

yeah i was just wondering how to form matrix