0

I am trying to show:

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

Could I have a hint?

I have tried rewriting $ \sum_{k=0}^{n} \sum_{r=k+1}^{n+1} \binom{n}{k} \binom{n+1}{r} = \sum_{k=0}^{n} \sum_{r=0}^{n-k} \binom{n}{k} \binom{n+1}{r} $

but I'm not sure what to do next. I can't flip the sums because one is dependent on the dummy variable of the other. I have looked through Concrete Mathematics for a suitable identity but cannot find one that applies. I have also thought about how I could split the double sum into a product of sums, but I cannot quite see it.

Oliver
  • 37
  • 3

1 Answers1

0

I think your idea is good. Just go one step further: $\sum_{k=0}^n\sum_{r=k+1}^{n+1}\binom{n}{k}\binom{n+1}{r}=\sum_{k=0}^n\sum_{r=0}^{n-k}\binom{n}{k}\binom{n+1}{r}=\sum_{k=0}^n\sum_{r=0}^{k}\binom{n}{k}\binom{n+1}{r}$ $k$ (First replace $r$ with $n+1-r$, then $k$ with $n-k$). Then $\sum_{k=0}^n\sum_{r=k+1}^{n+1}\binom{n}{k}\binom{n+1}{r}+\sum_{k=0}^n\sum_{r=0}^{k}\binom{n}{k}\binom{n+1}{r}=2^n2^{n+1}$.

dialegou
  • 47
  • 1