Not necessarily all recurrences, definitely linear ones, and also ones like never_stop mentioned which I suppose could be called “affine”. For matrix powers, we are formally using linear algebra but not really any deep results (essentially the def’n of matrix multiplication, and its associativity). Finding the matrix is just mechanical with the recurrence equation. As for going from a recurrence to a formula, I found knowing differential equation techniques helpful. You may also want to look at “generating functions” as they can make manipulating recurrences much easier.
1 Like
Can you give a link to your submission?
I didn’t understand why [f(2), f(1), f(0)] should be [4,2,1]
No of valid strings of length 0 should be 0 right ?
@abhi92 Good catch 
The partition into S only gives strings that have a 0 at the end.
Using arguments from the editorial one would be led to believe f(1) = 1.
But by setting f(1) = 2. We are ensuring that we calculate all the valid strings that end in 1.
1 Like