We've learnt on "discrete math" course at university how to derive closed form solutions to any similar recursive sequences using algebra and eigenvectors.

I remember that it's possible but I forgot all the required math :) Now that I googled it it's not THAT bad

https://medium.com/@andrew.chamberlain/the-linear-algebra-vi...

Of course the only use is to look smart once a decade when the subject comes up :)