This is probably beyond my ability and knowledge, but I played around with math and I stumped on this:
$$\Large \sum_{x=0}^{n-1}\left[\sum_{i=1}^k \binom{k}{i}x^{k-i}\right]=n^k\quad\quad \forall k\in\mathbb N$$
I am convinced this is true, but how can one proves that? What do I need to know to prove it?

Question

This is probably beyond my ability and knowledge, but I played around with math and I stumped on this: 
$$\Large \sum_{x=0}^{n-1}\left[\sum_{i=1}^k \binom{k}{i}x^{k-i}\right]=n^k\quad\quad \forall k\in\mathbb N$$
I am convinced this is true, but how can one proves that? What do I need to know to prove it?

geerky42 · Answer

It is true for first 5; $$\sum_{x=0}^{n-1}1=n$$$$\sum_{x=0}^{n-1}2x+1=n^2$$$$\sum_{x=0}^{n-1}3x^2+3x+1=n^3$$$$\sum_{x=0}^{n-1}4x^3+6x^2+4x+1=n^4$$$$\sum_{x=0}^{n-1}5x^4+10x^3+10x^2+5x+1=n^5$$

But of course this is not good enough to prove that this is true for all $k\in\mathbb N$...

unklerhaukus · Answer

induction?

anonymous · Answer

I am reminded of binomial theorem for the inner part.

ganeshie8 · Answer

I feel a combinatorics proof is possible as n^k reminds me of number of different strings of length "k" using "n"  characters with repetition

isaiah.feynman · Answer

Yup. Binomial theorem here.

anonymous · Answer

$$
\sum_{i=1}^k \binom{k}{i}x^{k-i}
=
\left(\sum_{i=0}^k \binom{k}{i}x^{k-i}\right) - x^k
=
(1+x)^k-x^k
$$

ganeshie8 · Answer

Yeah that telescopes nicely

geerky42 · Answer

lol just figured that out. Such beauty.

geerky42 · Answer

Pretty simply, thanks to Binomial Theorem. Thanks, everyone!