I've been trying to answer the second problem here:
And the hint is:
- I am having the following problem, If I expand the LHS, I get:
$$\sum_{i=1}^{k} {k+1 \choose i} S_n(i)={k+1 \choose 1} S_n(1)+{k+2 \choose i} S_n(2)+ \dots + {k+1 \choose k} S_n(k)$$ Which yields: $$ {k+1 \choose 1}(1+2+\dots +n) + {k+1 \choose 2} (1+2^2 + \dots + n^2)+ \dots + {k+1 \choose k}(1^k +2^k + \dots + n^k)\tag{$\star$}$$
- When I use the hint, I get:
$$(p+1)^{k+1}= {k+1 \choose 0}p^{k+1} + {k+1 \choose 1}p^{k}+ \dots + {k+1 \choose k+1}1 $$
Summing:
$${k+1 \choose 0}(1 + 2^{k+1}+\dots + n^{k+1} ) + {k+1 \choose 1}(1+2^{k}+\dots + n^k)+ \dots + {k+1 \choose k+1}(1+1+\dots + 1)\tag{$\heartsuit$} $$
- But if I subtract $(\star)$ from $(\heartsuit)$:
$$(\heartsuit)-(\star) ={k+1 \choose 0}(1 + 2^{k+1}+\dots + n^{k+1} )$$
And
$$(\heartsuit)-(\star) -(n+1) ={k+1 \choose 0}(1 + 2^{k+1}+\dots + n^{k+1} )-(n+1)\neq 0$$
I might me doing something silly and am unable to see what is it.
$$$$
Here is the solution for question $(2)$. We will follow the hint as suggested. Observe: $$ \sum_{p=1}^{n} (p+1)^{k+1} = \sum_{p=1}^{n} \sum_{i=0}^{k+1} \binom{k+1}{i} p^{i} = \sum_{i=0}^{k+1} \binom{k+1}{i} \sum_{p=1}^{n} p^{i} \\ = \sum_{i=0}^{k+1} \binom{k+1}{i} S_{n}(i) $$ This implies: $$ \sum_{i=1}^{k} \binom{k+1}{i} S_{n}(i) = \left[ \sum_{p=1}^{n} (p+1)^{k+1} \right] - S_{n}(k+1) - S_{n}(0) \\ = \left[ \sum_{p=1}^{n} (p+1)^{k+1} \right] - \left[ \sum_{p=1}^{n} p^{k+1} \right] - n = (n+1)^{k+1} - (n+1) $$ As desired.