# 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, 11 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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, 11 months 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, 11 months 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, 11 months 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, 11 months ago

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

- 4 years, 11 months ago