2
$\begingroup$

Came across a probability problem that is sort of challenging for a beginner in a sense that I may have not seen or came across a lot of binomial identities. What I am looking for is to see if there is any way to represent $\sum_{k=1}^{n} k^{2}$ in terms of binomial coefficient.

$\endgroup$
  • $\begingroup$ Do you mean $\sum_{k=1}^n k^2$? $\endgroup$ – Tavish May 29 at 18:02
  • $\begingroup$ @Tavish yes, sorry should've typed it up properly $\endgroup$ – Stacy May 29 at 18:22
6
$\begingroup$

Yes. Notice the following: $$k^2=k\cdot (k-1)+k=2\cdot \frac{k(k-1)}{2}+\binom{k}{1}=2\binom{k}{2}+\binom{k}{1}.$$ Doing this we have $$\sum _{k=1}^n\left (2\binom{k}{2}+\binom{k}{1}\right )=2\binom{n+1}{3}+\binom{n+1}{2},$$ using the Hockey-Stick identity.

Notice that this is part of a greater picture in which one can go from polynomials like $x^k$ to polynomials like $\binom{x}{k}$ as a change of basis.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much! This is exactly what i was looking for! $\endgroup$ – Stacy May 29 at 21:02
  • $\begingroup$ @Stacy You are welcome! $\endgroup$ – Phicar May 29 at 21:13
1
$\begingroup$

The identity

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

given in Phicar's answer can be found by counting the following in two ways:

The number of triples of integers $(x,y,z)$ with $x < z$ and $y < z$ where $x, y$ and $z$ are among the integers $0, \dots, n$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.