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

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestHere 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!

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

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.

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.

Log in to reply

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

Log in to reply