I was solving this problem(SUMMUL) on SPOJ. I got the idea that it can be solved using matrix exponentiation and after some intuition and observation, I figured out that the recurrence relation is-
F(n+1) = 3*F(n) - F(n-1) + n
But I do not have any proof for this. Is there any general/standard method to find the recurrence relations for these kind of problems?
I have seen a lot of coders using OEIS to find sequences and recurrence relations correlated with them. Though it’s not a standard way it gets the work done at times. So all you need is a brute force code to generate some initial terms. Plug them in OEIS and search if anything can be useful.
I wrote this brute force for the above code and this led me to this page and eventually on this page.
This was really helpful. I thought there should be a standard process as we may not always get the sequences on OEIS. Thank you 
Read this . There is a topic for matrix exponentiation and fibonacci , trifibonacci etc.
may be it can help
As far as I know, there is no hard and fast general way to find recurrences. Intuition, observation, creativity, and experience seems to be key.
Though after you have the recurrence, it can be probably be proved using the Principle of Mathematical Induction.