Mathematica failing to evaluate sum

I have some sums to simplify/evaluate, but for some reason I can't even get Mathematica to simplify relatively simple sums. For example, I tried to get Mathematica to simplify this sum:

$$\sum_{k=0}^{n} \sum_{r=k+1}^{n+1} \binom{n}{k} \binom{n+1}{r}$$

In this case, it is easy to prove that the sum is equal to $$2^{2n}$$.

I used FullSimplify[Sum[Binomial[n, k]*Binomial[n + 1, r], {k, 0, n}, {r, k + 1, n + 1}]], but Mathematica returns this:

I can't make any sense of the output. Did I do something wrong?

• Maple 2024 also can't compute. Mathematica is not a magic box that'll spit out a solution to any problem. Try AI and see if he(she) answers correctly? Commented Mar 31 at 18:27

\$Version

(* "14.0.0 for Mac OS X ARM (64-bit) (December 13, 2023)" *)

Clear["Global`*"]

sum[n_] = Sum[Binomial[n, k]*Binomial[n + 1, r], {k, 0, n}, {r, k + 1, n + 1}]

The result is a DifferenceRoot.

Generate a sequence and use FindSequenceFunction

sum2[n_] = FindSequenceFunction[sum /@ Range[6], n]

(* 4^n *)

Verifying the result outside of the range of the sequence,

And @@ Table[sum[n] == 4^n, {n, 0, 50}]

(* True *)

While sum is discrete, sum2 is continuous.

FunctionDomain[sum2[n], n]

(* True *)
• Can we compute sum without use: FindSequenceFunction ? Commented Mar 31 at 19:04