×

# sequence and series

For a non-negative integer k, $$S_{k}(n) = 1^k +2^k +3^k + \dots + n^k$$, then find : $$\displaystyle \sum_{k=0}^{r - 1} {r \choose k}S_{k}(n)$$

Note by Kushagraa Aggarwal
4 years ago

Sort by:

Here is a combinatorial solution.

For the first part of my solution, instead of $$S_k(n)$$, i will use $$Z_k(n) = n^k$$.

$$Z_k(n)$$ represents the number of ways to color a strip of $$k$$ blocks using $$n$$ colors.

The sum $$\sum\limits _{k=0}^{r-1} \binom{r}{k} Z_k(n)$$ represents the number of ways to choose some $$k$$ blocks of a strip of length $$r$$ and color them with $$n$$ colors. The number of blocks $$k$$ that we choose cannot equal $$r$$. If we were allowed to choose all blocks, then we can color all the non-chosen fields with a new color. Now, each block could get painted with each of $$n+1$$ colors, and the number of ways to do that is $$(n+1)^r$$. However, we must discard the cases where all blocks were painted using the old $$n$$ colors, since we cannot choose all blocks (remember $$k$$ goes up to $$r-1$$). So, we arrive at $$\sum\limits _{k=0}^{r-1} \binom{r}{k} Z_k(n) =(n+1)^r-n^r$$.

Since we have $$S_k(n) = \sum\limits _{m=1}^n Z_k(m)$$

We arrive at our solution:

$$\sum\limits _{k=0}^{r-1} S_k(n) \binom{r}{k}$$

$$= \sum\limits _{k=0}^{r-1} \binom{r}{k} \sum\limits _{m=1}^n Z_k(m)$$

$$= \sum\limits _{m=1}^n \sum\limits _{k=0}^{r-1} Z_k(m) \binom{r}{k}$$

$$= \sum\limits _{m=1}^n \left((m+1)^r-m^r\right)$$

$$=\sum\limits _{m=1}^n (m+1)^r-\sum\limits _{m=1}^n m^r$$

$$=\sum\limits _{m=2}^{n+1} m^r-\sum\limits _{m=1}^n m^r$$

Now most terms vanish,

$$=(n+1)^r-1^r$$

$$=(n+1)^r-1$$

And there you go! · 4 years ago

Note that $$(p+1)^k - p^k = \sum_{i=0}^{k-1} {k \choose i} p^i$$. Also note that $$\sum_{p=1}^{q-1} (p+1)^k - p^k= q^k - 1$$. Hence $$\sum_{p=1}^{q-1} \sum_{i=0}^{k-1} {k \choose i} p^i = q^k - 1$$.

We wish to determine $${r \choose 0} (1^0 + 2^0 + ... + n^0) + {r \choose 1} (1^1 + 2^1 + ... + n^1) + ... + {r \choose r-1} (1^{r-1} + 2^{r-1} + ... + n^{r-1} )$$. Note that this is equal to $$\sum_{p=1}^{n} \sum_{i=0}^{r-1} {r \choose i} p^i$$. Using our previously proved result, we conclude that the answer is $$(n+1)^{r} - 1$$. · 4 years ago

The 2nd math equation should be $$\displaystyle \sum_{p = 0}^{q-1} [(p+1)^k - p^k] = q^k - 0^k = q^k - 1$$.

EDIT: It should be $$\displaystyle \sum_{p = 1}^{q-1} [(p+1)^k - p^k] = q^k - 1^k = q^k - 1$$ as Sreejato B. has pointed out below. · 4 years ago

It has been corrected. I think you meant $$\sum_{p=1}^{q-1} [(p+1)^k - p^k]= q^k - 1^k= q^k - 1$$. Please correct me if I am wrong.

Update:- It has been corrected. · 4 years ago

May be you are also doing the same mistake as me. The answer given is $$(n + 1)^r - 1$$ · 4 years ago