1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial identity

  1. Mar 31, 2010 #1
    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.
     
  2. jcsd
  3. Mar 31, 2010 #2
    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: Mar 31, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook