f = k Binomial[n, k]

ansatz = (∑_(j = 0)^1)(∑_(i = 0)^1) a[i, j] F[n + j, 
                k + i] == 0

(∑_(j = 0)^1)(∑_(i = 0)^1) a[i, j] 
            F[n + j, k + i]/F[n, k] == 0

(∑_(j = 0)^1)(∑_(i = 0)^1) a[i, 
              j] (F[n + j, k + i]/F[n, k] /. {F[n_, k_] -> 
                    f}) == 0

sum = (∑_(j = 0)^1)(∑_(i = 0)^1) a[i, j] 
              FunctionExpand[
                F[n + j, k + i]/F[n, k] /. {F[n_, k_] -> f}] == 
        0

sum = Numerator[Together[sum[[1]]]]

liste = CoefficientList[sum, k]

lösung = 
      Solve[liste == 0, 
        Flatten[Table[a[i, j], {i, 0, 1}, {j, 0, 1}]]]

RE = 
      Numerator[
          Together[ansatz[[1]] /. lösung[[1]]]] == 
        0

Clear[kfreieRE]
\(kfreieRE[
        f_, {k_, kmax_}, {n_, nmax_}] := \(kfreieRE[
          f, {k, kmax}, {n, nmax}] = 
Module[{variablen, 
            sum, i, j, ansatz, liste, lösung, 
            RE}, 
variablen = 
            Flatten[Table[
                a[i, j], {i, 0, kmax}, {j, 0, 
                  nmax}]]; 
ansatz = 
            Sum[a[i, j]*F[n + j, k + i], 
{j, 0, nmax}, {i, 
                0, kmax}]; 
          sum = Sum[
              a[i, j]*FunctionExpand[\((f /. {k -> k + i, 
                          n -> n + j})\)/f], {j, 0, nmax}, {i, 0, 
                kmax}]; 
sum = 
            Numerator[Together[sum]]; 
liste = 
            CoefficientList[sum, k]; 
Off[
            Solve::"svars"]; 
lösung = 
            Solve[liste == 0, variablen]; 
On[
            Solve::"svars"]; 
lösung = 
            Simplify[lösung]; 
If[
            Union[Flatten[
                  Table[a[i, j] /. lösung[\([1]\)], {i, 0, 
                      kmax}, {j, 0, nmax}]]] === {0}, 
            Return["Es existiert keine solche Rekursion"]]; 
RE = 
            Numerator[
              Together[
                ansatz /. 
                  lösung[\([1]\)]]]; 
RE = 
            Collect[RE, F[__]]; 
RE = 
            Map[Factor, RE]; 
RE == 
            0
]\)\)

RE = kfreieRE[k Binomial[n, k], {k, 1}, {n, 1}]

kfreieRE[Binomial[n, k], {k, 1}, {n, 1}]

kfreieRE[Binomial[n, k]^2, {k, 2}, {n, 2}]

RE = RE[[1]] /. {F[n + j_. , k + i_. ] -> S[n + j]}

Clear[FasenmyerRE]
FasenmyerRE[f_, {k_, kmax_}, {n_, nmax_}] := 
      Module[{RE, tmp}, 
RE = 
          kfreieRE[f, {k, kmax}, {n, nmax}]; 
If[
          RE === "Es existiert keine solche Rekursion", 
          Return["Es existiert keine solche Rekursion"], 
          RE = RE[[1]]]; 
RE = 
          RE /. {F[n + j_. , k + i_. ] -> 
                S[n + j]}; 
tmp = 
          S[n + nmax] /. Solve[RE == 0, 
                S[n + nmax]][[1]]; 
RE = 
          Denominator[tmp]*S[n + nmax] - 
            Numerator[tmp]; 
RE = 
          Collect[RE, S[___]]; 
Map[Factor, RE] == 
          0
]

FasenmyerRE[k Binomial[n, k], {k, 1}, {n, 1}]

FasenmyerRE[Binomial[n, k], {k, 1}, {n, 1}]

FasenmyerRE[Binomial[n, k]^2, {k, 2}, {n, 2}]

FasenmyerRE[(((-1))^k) Binomial[n, k]^2, {k, 2}, {n, 
        2}]

FasenmyerRE[
      Binomial[n, k] Binomial[-n - 1, k] (((((1 - x)/2)))^k), {k, 
        1}, {n, 2}]

FasenmyerRE[(1/(2^n)) (((-1))^k) Binomial[n, k] 
        Binomial[2  n - 2  k, n] (x^(n - 2  k)), {k, 1}, {n, 2}]