Let $\mathbb{S}=\{a_1,\ a_2,\ \cdots,\ a_n\}$ where every element $a_i\in\{1,\ 2,\ \cdots,\ k\}$. Find the number of $\mathbb{S}$ which has an even number of $1$s.
Let the number of $\mathbb{S}$ which has an even and an odd number of $1$ be $E_n$ and $O_n$ respectively, then $$E_n + O_n = k^n$$
because there are totally $k^n$ possible $\mathbb{S}$.
Now consider the relation between an $n$-element $\mathbb{S}_n$ and an $\mathbb{S}_{n-1}$ of $(n-1)$ elements. If $\mathbb{S}_{n-1}$ has odd number of $1$s, then $\mathbb{S}_n$ needs to append a $1$ in order to have even number of $1$. If $\mathbb{S}_{n-1}$ has even number of $1$, then $\mathbb{S}_n$ has $(k-1)$ choices to select an element not equal to $1$. Therefore, $$E_n = O_{n-1} + (k-1) E_{n-1}$$
Because $O_{n-1}+E_{n-1}=k^{n-1}$, this relation can be rewritten as $$E_n =(k^{n-1}-E_{n-1}) + (k-1)E_{n-1}=(k-2)E_{n-1}+k^{n-1}$$
When $n=1$, $E_1=k-1$. Then $$\begin{align*}E_n=\ &(k-2)E_{n-1} + k^{n-1}\\=\ &(k-2)((k-2)E_{n-2}+k^{n-2})+k^{n-1}\\=\ &(k-2)^2E_{n-2}+(k-2)k^{n-2} + k^{n-1}\\=\ & \cdots \\=\ &(k-2)^{n-1}(k-1) + (k-2)^{n-2}k+\cdots +(k-2)k^{n-2}+k^{n-1}\\=\ &k^{n-1}\frac{1-\left(\frac{k-2}{k}\right)^n}{1-\frac{k-2}{k}}+(k-2)^n\\=\ &\boxed{\frac{k^n+(k-2)^n}{2}} \end{align*}$$