Needs["SpecialFunctions`"]

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]]]
]

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

Clear[PrimDispersion]
PrimDispersion[q_, r_, k_] := 
      Module[{s, t, n, a, b, c, d, j}, 
s = 
          Collect[q, k]; 
t = 
          Collect[r, k]; 
n = 
          Exponent[s, k]; 
If[
          n === 0  ||  Not[n == Exponent[t, k]], 
          Return[{}]]; 
a = 
          Coefficient[s, k, n]; 
b = 
          Coefficient[s, k, n - 1]; 
c = 
          Coefficient[t, k, n]; 
d = 
          Coefficient[t, k, n - 1]; 
j = 
          Together[(b*c - a*d)/(a*c*n)]; 
If[
          Not[IntegerQ[j] &&  j ≥ 0], 
          Return[{}]]; 
If[
          Together[c*s - a*(t /. k -> k + j)] === 0, Return[{j}], 
          Return[{}]]
]

Clear[DispersionsMenge]
DispersionsMenge[q_, r_, k_] := 
      Module[{f, g, m, n, i, j, result, dis, op1, 
          op2}, 
f = Factor[q]; 
g = 
          Factor[r]; 
If[Not[Head[f] === Times], m = 1, 
          m = Length[f]]; 
If[Not[Head[g] === Times], 
          n = 1, n = 
            Length[g]]; 
result = {}; 
Do[
If[Head[f] === Times, 
            op1 = f[[i]], op1 = f]; 
If[
            Head[op1] === Power, 
            op1 = op1[[1]]]; 
Do[
If[
              Head[g] === Times, op2 = g[[j]], 
              op2 = g]; 
If[Head[op2] === Power, 
              op2 = op2[[1]]]; 
dis = 
              PrimDispersion[op1, op2, k]; 
If[
              Not[dis === {}], 
              AppendTo[result, dis[[1]]]], 
{j, 1, 
              n}], 
{i, 1, m}]; 
Union[
          result]
]

Clear[SumRekursion]
\(SumRekursion[F_, k_, S_[n_]] := 
      Module[{a, σ, ratk, ratn, rat, nenner, u, v, M, dis, h, j, deg, 
          rec, sol, A, B, CC, gcd, α, g, 
          RE}, 
RE = {}; 
Do[
ratk = 
            SimplifyCombinatorial[\((F /. k -> k + 1)\)/
                F]; 
ratn = 
            SimplifyCombinatorial[\((F /. n -> n + 1)\)/
                F]; 
nenner = 
            1 + Sum[σ[j]*
                  Product[ratn /. n -> n + i, {i, 0, j - 1}], {j, 
                  J}]; 
rat = 
            Together[
              ratk*\((nenner /. k -> k + 1)\)/
                  nenner]; 
u = 
            Numerator[rat]; 
v = 
            Denominator[rat]; 
If[
            Not[PolynomialQ[u, k]\  && PolynomialQ[v, k]], 
            Return[]]; 
M = 
            DispersionsMenge[u /. k -> k - 1, v, 
              k]; 
dis = Max[M]; 
h = 
            PolynomialGCD[Product[u /. k -> k - 1 - j, {j, 0, dis}], 
              Product[v /. k -> k + j, {j, 0, 
                  dis}]]; 
If[
            dis == 0, 
A = 
              Together[
                u/\((h /. 
                      k -> k + 1)\)]; 
B = \(-Together[
                  v/h]\); 
CC = v, 
A = 
              h*u; 
B = \(-\((h /. k -> k + 1)\)\)*
                v; 
CC = 
              h*\((h /. k -> k + 1)\)*v]; 
gcd = 
            PolynomialGCD[A, B, CC]; 
A = 
            Together[A/gcd]; 
B = 
            Together[B/gcd]; 
CC = 
            Together[CC/gcd]; 
deg = 
            GradSchranke[A, B, CC, k]; 
If[
            deg >= 0, 
g = 
              Sum[α[j]*k^j, {j, 0, deg}]; 
rec = 
              Collect[A*\((g /. k -> k + 1)\) + B*g - CC, 
                k]; 
sol = 
              Solve[CoefficientList[rec, k] == 0, 
                Union[Table[α[j], {j, 0, deg}], 
                  Table[σ[j], {j, 1, J}]]]; 
If[
              Not[sol === {}], 
RE = 
                S[n] + Sum[σ[j]*S[n + j] /. sol[\([1]\)], {j, 1, 
                      J}]; 
RE = 
                Numerator[Together[RE]]; 
RE = 
                Collect[RE, S[___]]; 
RE = 
                Map[Factor, 
                  RE]; 
Return[]
]
]
, {J, 1, 5}]; 
If[
          Not[PolynomialQ[u, k]\  && PolynomialQ[v, k]], 
          Return["Eingabe ist kein hypergeometrischer Term"], 
If[
            RE === {}, 
"Es gibt keine Rekursion der Ordnung 5", RE == 0]]
]\)

SumRekursion[Binomial[n, k], k, S[n]]

SumRekursion[Binomial[n, k]^2, k, S[n]]

SumRekursion[(((-1))^k) Binomial[n, k]^2, k, S[n]]

SumRekursion[Binomial[n, k]^3, k, S[n]]

SumRekursion[Binomial[n, k]^4, k, S[n]]

Zb[Binomial[n, k]^3, k, n, 2]

Zb[Binomial[n, k]^4, k, n, 2]

Zb[Binomial[n, k]^5, k, n, 3]

SumRekursion[
      Binomial[n, k] Binomial[-n - 1, k] (((((1 - x)/2)))^k), k, 
      P[n]]

SumRekursion[((((-1))^k)/(k!)) Binomial[n + α, n - k] 
        (x^k), k, L[n]]