Binomial coefficients?

• Apr 23rd 2009, 07:16 AM
fardeen_gen
Binomial coefficients?
Let k and n be positive integers and put S(k) = 1^k + 2^k + 3^k + ... + n^k.

Show that (m + 1)C(1)S(1) + (m + 1)C(2)S(2) + ... + (m + 1)C(m)S(m) = (n + 1)^(m + 1) - (n + 1)

NOTE: (m + 1)C(1) is (m + 1) choose 1
S(k) - k is subscript
• Apr 23rd 2009, 09:00 AM
PaulRS
In this post we we'll take: $\displaystyle 0^0=1$ to shorten the thing.

Note that: $\displaystyle \sum\limits_{j = 1}^n {\left[ {\left( {j + 1} \right)^k - j^k } \right]} = \left( {n + 1} \right)^k - 1$

By the Binomial Theorem: $\displaystyle \sum\limits_{j = 1}^n {\left[ {\sum\limits_{s = 0}^k {\binom{k}{s}\cdot j^s } - j^k } \right]} =\sum\limits_{j = 1}^n {\left[ {\sum\limits_{s = 0}^{k-1}{\binom{k}{s}\cdot j^s }} \right]} = \left( {n + 1} \right)^k - 1$

Now reverse the Order of the sums: $\displaystyle \sum\limits_{s = 0}^{k-1} {\binom{k}{s}\cdot\left[ {\sum\limits_{j = 1}^{n}{ j^s }} \right]} = \left( {n + 1} \right)^k - 1$

Note that for $\displaystyle s=0$: $\displaystyle \binom{k}{s}\cdot \sum\limits_{j = 1}^{n}{ j^s }=n$ thus $\displaystyle \sum\limits_{s = 1}^{k-1} {\binom{k}{s}\cdot\left[ {\sum\limits_{j = 0}^{n}{ j^s }} \right]} = \left( {n + 1} \right)^k - (n+1)$ (Nod)