Prove $\sum_{x=1}^{X} \sum_{y=1}^Y {Y \choose y} \times (x-1)^{Y-y} = X^Y$

Question

I accidentally find this property, $\sum_{x=1}^{X} \sum_{y=1}^Y {Y \choose y} \times (x-1)^{Y-y} = X^Y$, when doing a brain-teaser. I only tried up to y=3, but it seems to be true for all X and Y. Can anyone give an induction prove? (or any direct prove is also appreciated)

Edit: It is ${Y \choose y}$ sorry!

Compute the inner sum (using the binomial formula) and see some telescoping. — metamorphy, Sep 06 '23 at 02:49

score 3 · Accepted Answer · answered Sep 06 '23 at 02:57

We can use the binomial theorem

$$(a + b)^n = \sum_{k=0}^{n} {n \choose k} a^{n-k} b^k$$

In our case, we have:

$$(x-1 + 1)^Y = \sum_{y=0}^{Y} {Y \choose y} (x-1)^{Y-y}\cdot 1^y$$ $$x^Y = (x-1)^Y+\sum_{y=1}^{Y} {Y \choose y} (x-1)^{Y-y}$$ Therefore, $$\sum_{x=1}^{X} \sum_{y=1}^Y {Y \choose y} \times (x-1)^{Y-y}=\sum_{x=1}^{X}[x^Y- (x-1)^Y]= X^Y$$

Prove $\sum_{x=1}^{X} \sum_{y=1}^Y {Y \choose y} \times (x-1)^{Y-y} = X^Y$

1 Answers1