Combinatorial identity

  • #1

Main Question or Discussion Point

Hi, I would like some help in proving the following identity:

[tex]\sum_{x=0}^{n}x^3 = 6\binom{n+1}{4} + 6\binom{n+1}{3} + \binom{n+1}{2}[/tex]

I tried doing it by induction but that did not go well (perhaps I missed something). Someone told me to use the fact that [tex]\binom{x}{0}, \binom{x}{1},...,\binom{x}{k}[/tex] span the space of polynomials of degree k or less [tex]\mathbb{R}_k[x][/tex], but I didn't really see how to use that. Any help would be welcome, but I'd rather it would not be the whole solution but rather hints.

Thanks a lot and have a good day.
 

Answers and Replies

  • #2
430
3
From the hint you know that you can write the polynomial x^3 as:
[tex]x^3 = a_0\binom{x}{0} + a_1\binom{x}{1} + a_2\binom{x}{2} + a_3\binom{x}{3}[/tex]
for constants [itex]a_0,\ldots,a_3[/itex]. By substituting appropriate values for x you should be able to work out these constants. By plugging this expression into your summation you should be able to arrive at something you can compute.

Also for the solution you need to remember the identity:
[tex]\binom{n+1}{k+1} = \sum_{i=0}^n \binom{n}{k}[/tex]
where n is an integer.

EDIT: By the way induction also works fine if you express n^3 as a suitable linear combination of binomial coefficients.
 
Last edited:

Related Threads for: Combinatorial identity

Replies
8
Views
712
Replies
1
Views
1K
  • Last Post
Replies
6
Views
2K
Replies
5
Views
787
Replies
2
Views
2K
  • Last Post
Replies
7
Views
13K
Replies
2
Views
2K
Top