Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
3 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

Sort by:

Top Newest

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!

Ivan Stošić - 4 years, 3 months ago

Log in to reply

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\).

Sreejato Bhattacharya - 4 years, 3 months ago

Log in to reply

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.

Jimmy Kariznov - 4 years, 3 months ago

Log in to reply

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.

Sreejato Bhattacharya - 4 years, 3 months ago

Log in to reply

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

Kushagraa Aggarwal - 4 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...