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 ago

No vote yet
3 votes

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 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 ago

Log in to reply

@Sreejato Bhattacharya 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 ago

Log in to reply

@Jimmy Kariznov 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 ago

Log in to reply

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

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...