7

I am looking in Gradsteyn and Ryzhik 7th edition and formula 0.241.11 is the following finite sum $$\sum_{k = 0}^i{\binom{i + k}{k}^{i - k}k} = (i + 1)4^i - (2i + 1)\binom{2i}{i}.$$ However, after looking at a few values of $i$ it appears that this equation is not correct. For example, for $i = 1$ we get $$\text{LHS} = \binom{1}{0}^1(0) + \binom{2}{1}^0(1) = 1 \quad\text{and}\quad \text{RHS} = (2)(4) - (3)\binom{2}{1} = 2.$$ Is this an error?

Paul
  • 91
  • 1
    With how low the exponent $i - k$ is in the book, and how there's already a typo with an $h$ in the binomial coefficient in the formula there, it wouldn't surprise me if the exponent was supposed to be on the $k$ instead. For $i = 1$ it then works out, though I haven't looked further. Good catch though! – Bruno B Jul 07 '23 at 14:21
  • I thought that might be the case too, but that doesn't hold for $i = 2$. – Paul Jul 07 '23 at 14:46

2 Answers2

7

Apparently, the correct formula is $$ \sum_{k = 0}^i{\binom{i + k}{k}2^{i - k}k} = (i + 1)4^i - (2i + 1)\binom{2i}{i}. $$

Gonçalo
  • 9,312
  • Oh that makes sense with how it's formatted in the book, the low exponent was just an exponent tied to a number that didn't show up huh. – Bruno B Jul 07 '23 at 14:55
  • The expression you gave should be true, if I didn't do any mistake in my answer below. – Bruno B Jul 07 '23 at 15:48
  • 1
    Recognising the pattern was half the battle to be fair so your laziness wasn't in vain, wouldn't have done it without you ;) – Bruno B Jul 07 '23 at 16:04
6

Using this answer: https://math.stackexchange.com/a/128932/1104384, I was able to figure out a proof for the correct expression that Gonçalo gave!

From the post I linked (looking at the intermediate steps), one has: $$\tag{$*$}\sum_{k=1}^{n+1}2^{n+1-k}k\binom{n+k}n = (n+1)\left(2^{2n+1}-\binom{2n+1}{n+1}\right)$$ Thus: $$\begin{split} \sum_{k = 1}^n{\binom{n + k}{k}2^{n - k}k} &= \frac{1}{2}\left(\sum_{k = 1}^n{\binom{n + k}{k}2^{n+1 - k}k}\right)\\ &= \frac{1}{2}\left(\sum_{k = 1}^{n+1}{\binom{n + k}{k}2^{n+1 - k}k} - (n+1)\binom{2n+1}{n+1}\right)\\ &\overset{(*)}{=} \frac{1}{2}\left((n+1)\left(2^{2n+1}-\binom{2n+1}{n+1}\right)- (n+1)\binom{2n+1}{n+1}\right)\\ &= (n+1)4^n - (n+1)\binom{2n+1}{n+1}\\ &= (n+1)4^n - (2n+1)\binom{2n}{n} \end{split}$$ which is the result we expected.

Bruno B
  • 5,027