Clear[GradSchranke]
GradSchranke[A_, B_, C_, k_] := 
      Module[{pol1, pol2, deg1, deg2, a, b}, 
pol1 = 
          Collect[A - B, k]; 
pol2 = 
          Collect[A + B, k]; 
If[pol1 === 0, deg1 = -1, 
          deg1 = Exponent[pol1, k]]; 
If[pol2 === 0, 
          deg2 = -1, deg2 = Exponent[pol2, k]]; 
If[
          deg1 ≤ deg2, Print["Teil 1"]; 
          Return[Exponent[C, k] - deg2]]; 
a = 
          Coefficient[pol1, k, deg1]; 
If[deg2 < deg1 - 1, 
          b = 0, b = Coefficient[pol2, k, deg2]]; 
If[
          Not[IntegerQ[-2*b/a] && -2*b/a ≥ 0], 
          Print["Teil 2a"]; Return[Exponent[C, k] - deg1 + 1], 
          Print["Teil 2b"]; 
          Return[Max[-2*b/a, 
              Exponent[C, k] - deg1 + 1]]]
]

GradSchranke[k - n, -(k + 1), k + 1, k]

GradSchranke[
      k (((k + 1))^2), -k (k + 1), (k^2) (k + 1), 
      k]

GradSchranke[k + 1, -1, 1, k]

Clear[REtoPol]
\(REtoPol[A_, B_, C_, k_] := 
      Module[{\ deg, g, a, j, rec, sol, result}, 
deg = 
          GradSchranke[A, B, C, k]; 
If[deg < 0, 
          Return["keine Polynomlösung"]]; 
g = Sum[a[j]*k^j, {j, 0, deg}]; 
rec = 
          Collect[A*\((g /. k -> k + 1)\) + B*g - C, 
            k]; 
sol = 
          Solve[CoefficientList[rec, k] == 0, 
            Table[a[j], {j, 0, deg}]]; 
If[sol === {}, 
          Return["keine Polynomlösung"]]; 
result = \(g /. sol[\([1]\)]\) /. 
            a[_] -> 0
]\)

REtoPol[k - n, -(k + 1), k + 1, k]

REtoPol[k (((k + 1))^2), -k (k + 1), (k^2) (k + 1), 
      k]

REtoPol[k + 1, -1, 1, k]

a = (1/(k + 1))

rat = FunctionExpand[(((a /. k -> k + 1))/a)]

u = Numerator[rat];  v = Denominator[rat];

h = 1;

RE = 
      h*u*g[k + 1] - (h /. k -> k + 1)*v*g[k] == 
        h*(h /. k -> k + 1)*v

GradSchranke[Coefficient[RE[[1]], g[k + 1]], 
      Coefficient[RE[[1]], g[k]], RE[[2]], k]

REtoPol[Coefficient[RE[[1]], g[k + 1]], 
      Coefficient[RE[[1]], g[k]], RE[[2]], k]