Now please don't go downvoting the blog as there already are blogs and editorials on this, I know, please read my question though

So, I solved this problem using a 2d dp — dp[n][2] which was the solution I found in almost all of the editorials and blogs. But here's something interesting my friend found,

dp[i] = 6*dp[i-1] - 7*dp[i-2]

Apparently this recursive relation also solves the problem...

So, does anybody have an intuition for this?
I found it here

I would also like to tag the person who wrote this code — Jonathan_Uy