This is just an extended comment. 

There is no need to invoke the algebraic dependency search. The recurrence can be found by directly constructing Groebner basis $B$ under any term order, in which $n$ has the highest weight and $y_m$ corresponding to $f$ with largest index has the second highest weight. Then in $B$ we are interested in polynomials with degree of $n$ equal 0 and degree of $y_m$ equal 1.

Here is a [sample Sage code](https://sagecell.sagemath.org/?z=eJx9UsFu2zAMvQfIPxDowVLteHGGXQzk6ksu7bBLE3iBElEuEYcuZGerUeTfR9kD4rbDCBimRL1H8pF3YNr2ckbonk0H_Y5KWINTvLAx6fnMFpmc1SqB2pwP1gAnfQ7q6z3H3_R9v1uWEIPinyv5sXyrcJmVghQsOnDEdu8qZQudz2cgZhMohNIW4_Ekfja6v5-pRvjhL_j3abCNxB-auufmTKb-Tlypx8fkFNs4i7Mk6qOk8Rb9OiL-VeNrpG_QXqCbtEJuld7li6y8hXgaehd5kshOdJD2S1hAoTimRGTJKbalBtd4ICAGb7hCdYozDRN029QBv6jSY4PO0ZGQO_XWhxz58qq__DOQXUfiKhBvUrJoavWk08o3eGD0-4NpSSoFclClFiuPqFiv10swbG9XA5tcT_sRiBQ1ETTYiyfJ7qJBOin4TfS8TqULdgcHNJeOXC_vsZV6TUcNQzMwXoLfvkdstp-Htd2GYf1_UCM23demw9c9mzO2QUUXhT0MtS3oqqPP2ltdfiQJqyVUzptjKHDvCGurPuTy2F08wy7wawFEsrhDbiUEqtXjNNqQSjqd5DhBPGzrfHbb60z_Afyg4Iw=&lang=sage&interacts=eJyLjgUAARUAuQ==), which as an example processes the same recurrence as in Theorem 6:
$$F (n, f (n-1), f (n-2)) := f(n-1)(n^2 + n + 2) + f (n-2)(3n + 5).$$

It finds 3 independent solutions of the minimal possible order 4:
$$f(n) = \tfrac{-16 f(n-3) f(n-1)^{3} + 24 f(n-4) f(n-1)^{3} + 56 f(n-3) f(n-2) f(n-1)^{2} - 84 f(n-4) f(n-2) f(n-1)^{2} - 366 f(n-4) f(n-3) f(n-1)^{2} + 189 f(n-4)^{2} f(n-1)^{2} - 24 f(n-2)^{3} f(n-1) + 444 f(n-3) f(n-2)^{2} f(n-1) + 174 f(n-4) f(n-2)^{2} f(n-1) - 164 f(n-3)^{2} f(n-2) f(n-1) - 1342 f(n-4) f(n-3) f(n-2) f(n-1) + 822 f(n-4)^{2} f(n-2) f(n-1) + 1092 f(n-3)^{3} f(n-1) + 312 f(n-4) f(n-3)^{2} f(n-1) - 567 f(n-4)^{2} f(n-3) f(n-1) - 252 f(n-2)^{4} + 230 f(n-3) f(n-2)^{3} + 341 f(n-4) f(n-2)^{3} - 2004 f(n-3)^{2} f(n-2)^{2} + 2348 f(n-4) f(n-3) f(n-2)^{2} - 2338 f(n-4)^{2} f(n-2)^{2} - 4954 f(n-3)^{3} f(n-2) + 12017 f(n-4) f(n-3)^{2} f(n-2) - 3672 f(n-4)^{2} f(n-3) f(n-2) - 7888 f(n-3)^{4} + 3672 f(n-4) f(n-3)^{3}}{24 f(n-4) f(n-2) f(n-1) - 16 f(n-2)^{3} - 4 f(n-4) f(n-2)^{2} - 27 f(n-4)^{2} f(n-2) - 54 f(n-3)^{3} + 27 f(n-4) f(n-3)^{2}},$$
$$f(n) = \tfrac{24 f(n-3) f(n-2) f(n-1)^{2} - 12 f(n-4) f(n-2) f(n-1)^{2} - 186 f(n-4) f(n-3) f(n-1)^{2} + 123 f(n-4)^{2} f(n-1)^{2} - 16 f(n-2)^{3} f(n-1) + 116 f(n-3) f(n-2)^{2} f(n-1) + 34 f(n-4) f(n-2)^{2} f(n-1) - 52 f(n-3)^{2} f(n-2) f(n-1) - 322 f(n-4) f(n-3) f(n-2) f(n-1) + 122 f(n-4)^{2} f(n-2) f(n-1) - 36 f(n-3)^{3} f(n-1) + 600 f(n-4) f(n-3)^{2} f(n-1) - 369 f(n-4)^{2} f(n-3) f(n-1) - 36 f(n-2)^{4} + 90 f(n-3) f(n-2)^{3} + 3 f(n-4) f(n-2)^{3} - 300 f(n-3)^{2} f(n-2)^{2} + 324 f(n-4) f(n-3) f(n-2)^{2} - 78 f(n-4)^{2} f(n-2)^{2} - 1238 f(n-3)^{3} f(n-2) + 2055 f(n-4) f(n-3)^{2} f(n-2) - 648 f(n-4)^{2} f(n-3) f(n-2) - 1392 f(n-3)^{4} + 648 f(n-4) f(n-3)^{3}}{8 f(n-3)^{2} f(n-1) - 12 f(n-4) f(n-2)^{2} + 51 f(n-4)^{2} f(n-2) - 58 f(n-3)^{3} - 51 f(n-4) f(n-3)^{2}},$$
$$f(n) = \tfrac{4 f(n-3) f(n-1)^{2} - 3 f(n-4) f(n-1)^{2} - 2 f(n-2)^{2} f(n-1) + 10 f(n-3) f(n-2) f(n-1) - 2 f(n-4) f(n-2) f(n-1) - 14 f(n-3)^{2} f(n-1) + 9 f(n-4) f(n-3) f(n-1) - 3 f(n-2)^{3} + 16 f(n-3) f(n-2)^{2} - 18 f(n-4) f(n-2)^{2} + 9 f(n-3)^{2} f(n-2)}{2 f(n-3) f(n-2) - 3 f(n-4) f(n-2) + 3 f(n-3)^{2}},$$
the last of which matches the one given in the paper.