Factorization of a Polynomials 
Does Mathematical induction work? 
 A: One trick you can use here is to use the fact that all roots of $1+\cdots+x^k$ are distinct and known. Since
$$
1+\cdots+x^k = \frac{1-x^{k+1}}{1-x},
$$
the $k$ roots of $1+\cdots+x^k$ are the $(k+1)$th roots of unity different from $1$. It remains to check that each such root is a root of $1 + x^n + \cdots + x^{kn}$. If we put $y = x^n$, then the latter polynomial is just $1+\cdots+y^k$, so the roots of $1 + x^n + \cdots + x^{kn}$ are all numbers $x$ such that $y = x^n$ is a $(k+1)$th root of unity different from $1$. Therefore, we have to show that if $\omega^{k+1} = 1$ and $\omega \neq 1$ then $(\omega^n)^{k+1} = 1$ and $\omega^n \neq 1$. The first item is easy: $(\omega^n)^{k+1} = (\omega^{k+1})^n = 1^n = 1$. For the second item, we can try to show the contrapositive: $\omega^n = 1$ implies $\omega = 1$. This is actually not always true! So your claim actually doesn't hold for all values of $k,n$.
In order to determine when the claim does hold, let $\alpha$ be a primitive $(k+1)$th root of unity, and let $\omega = \alpha^r$, where $1 \leq r \leq k$. We want to avoid $\omega^n = 1$. Now $\omega^n = \alpha^{rn}$, so $\omega^n = 1$ iff $k+1 \mid rn$. We can find such $r$ whenever $(n,k+1) > 1$. Therefore your claim is true exactly when $(n,k+1) = 1$.
A: EDIT: this is incorrect as I had $x-1$ rather than $x^n-1$ in the denominator of $g$. It was only after seeing Yuval's solution that I copped this mistake.
Let $f(x)$ be the first expression and $g(x)$ the second.
Note that $x=1$ is a root of neither. Both are geometric series. In particular,
$$f(x)=\frac{x^{k+1}-1}{x-1}.$$
Therefore the roots of $f(x)$ are the $(k+1)th$ roots of unity --- except for $x=1$.
Now note that, using the geometric series again, we have
$$g(x)=\frac{(x^n)^{k+1}-1}{x-1}=\frac{(x^{k+1})^n-1}{x-1}.$$
Note that all of the $(k+1)$-th roots of unity (bar $x=1$) are roots of $g$.
Hence roots of $f$ are roots of $g$ and by the factor theorem factors of $f$ are factors of $g$.
