sequence and series

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

#Combinatorics #MathProblem #Math

Note by Kushagraa Aggarwal
7 years, 10 months ago

No vote yet
3 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Here is a combinatorial solution.

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

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

The sum ∑k=0r−1(rk)Zk(n) \sum\limits _{k=0}^{r-1} \binom{r}{k} Z_k(n) represents the number of ways to choose some k k blocks of a strip of length r r and color them with n n colors. The number of blocks k k that we choose cannot equal r 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 n+1 colors, and the number of ways to do that is (n+1)r (n+1)^r . However, we must discard the cases where all blocks were painted using the old n n colors, since we cannot choose all blocks (remember kk goes up to r−1r-1). So, we arrive at ∑k=0r−1(rk)Zk(n)=(n+1)r−nr \sum\limits _{k=0}^{r-1} \binom{r}{k} Z_k(n) =(n+1)^r-n^r .

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

We arrive at our solution:

∑k=0r−1Sk(n)(rk) \sum\limits _{k=0}^{r-1} S_k(n) \binom{r}{k}

=∑k=0r−1(rk)∑m=1nZk(m) = \sum\limits _{k=0}^{r-1} \binom{r}{k} \sum\limits _{m=1}^n Z_k(m)

=∑m=1n∑k=0r−1Zk(m)(rk) = \sum\limits _{m=1}^n \sum\limits _{k=0}^{r-1} Z_k(m) \binom{r}{k}

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

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

=∑m=2n+1mr−∑m=1nmr =\sum\limits _{m=2}^{n+1} m^r-\sum\limits _{m=1}^n m^r

Now most terms vanish,

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

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

And there you go!

Ivan Stošić - 7 years, 10 months ago

Note that (p+1)k−pk=∑i=0k−1(ki)pi (p+1)^k - p^k = \sum_{i=0}^{k-1} {k \choose i} p^i . Also note that ∑p=1q−1(p+1)k−pk=qk−1 \sum_{p=1}^{q-1} (p+1)^k - p^k= q^k - 1 . Hence ∑p=1q−1∑i=0k−1(ki)pi=qk−1 \sum_{p=1}^{q-1} \sum_{i=0}^{k-1} {k \choose i} p^i = q^k - 1.

We wish to determine (r0)(10+20+...+n0)+(r1)(11+21+...+n1)+...+(rr−1)(1r−1+2r−1+...+nr−1) {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 ∑p=1n∑i=0r−1(ri)pi \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(n+1)^{r} - 1.

Sreejato Bhattacharya - 7 years, 10 months ago

Log in to reply

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

EDIT: It should be ∑p=1q−1[(p+1)k−pk]=qk−1k=qk−1\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 - 7 years, 10 months ago

Log in to reply

It has been corrected. I think you meant ∑p=1q−1[(p+1)k−pk]=qk−1k=qk−1 \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 - 7 years, 10 months ago

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

kushagraa aggarwal - 7 years, 10 months ago
×

Problem Loading...

Note Loading...

Set Loading...