Olimpíadas ⇒ Somatório - Identidade interessante

[Andre13000]

Prove que

[tex3]S_n=x^{n+1}+x^n+\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}S_k[/tex3]

Onde [tex3]S_k=1^k+2^k+\dots+x^k[/tex3]

[Auto Excluído (ID:12031)]

Uma ideia que eu tive é a de fazer:
[tex3]\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}S_k = \sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}(S_k-1+1)[/tex3]
[tex3]\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}(S_k-1) + \sum_{k=1}^n {n\choose k}(-1)^kx^{n-k} [/tex3]
[tex3]\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}(S_k-1) + (x-1)^n [/tex3]
e continuar até zerar o termo de dentro:

[tex3]\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}(S_k-1-2^k + 2^k) + (x-1)^n [/tex3]
[tex3]\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}(S_k-1-2^k) + (x-2)^n + (x-1)^n [/tex3]
você terminaria com

[tex3](x-1)^n + (x-2)^n + (x-3)^n + ... +1[/tex3]
mas não ficaria com o [tex3]x^{n+1}[/tex3] no começo

[Andre13000]

[tex3]f(x)=x^n\\
f(x-1)=(x-1)^n=\sum_{k=0}^n {n\choose k}(-1)^kx^{n-k}\\
f(x-2)=(x-2)^n=\sum_{k=0}^n{n\choose k}(-1)^k x^{n-k} 2^k\\
f(x-3)=(x-3)^{n}=\sum_{k=0}^n{n\choose k}(-1)^k x^{n-k} 3^k\\
\vdots\\
f(1)=(x-(x-1))^n=\sum_{k=0}^n{n\choose k}(-1)^k x^{n-k} (x-1)^k\\
f(0)=(x-x)^n=\sum_{k=0}^n{n\choose k}(-1)^k x^{n-k} x^k\\
\sum_{r=0}^x f(r)=x^n+\sum_{k=0}^n{n\choose k}(-1)^k x^{n-k}{ \sum_{r=1}^x r^k}\\\\
S_n=x^n+\sum_{k=0}^n {n\choose k}(-1)^kx^{n-k}S_k\\
S_n=x^{n+1}+x^n+\sum_{k=1}^n {n\choose k}(-1)^kx^{n-k}S_k[/tex3]