Induction problem prove that at least one of the coefficients Cn is even

Question

For $n \in \mathbb{N}$ regard $1+x+x^2$ as a polynomial, i.e.,

$$(1+x+x^2)^n = \sum C_n(x^n)$$

with $C_n \in \mathbb{N}$, and prove that at least one of the coefficients $C_n$ is even.

I really don't know how to solve this one

I know that the sum of $C_nx^n$ can be written like this:

$$C_0 + C_1x + C_2x^2 +C_3x^3+\cdots$$

Please help thank you very much

Answer 1

You can use the binomial theorem ($(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$) for see the proposition is true, for $n\geq 2$, See a few examples

\begin{align*} (1+x+x^2)^2&=1 + 2 x + 3 x^2 + 2 x^3 + x^4\\ (1+x+x^2)^3&=1 + 3 x + 6 x^2 + 7 x^3 + 6 x^4 + 3 x^5 + x^6\\ (1+x+x^2)^4&=1 + 4 x + 10 x^2 + 16 x^3 + 19 x^4 + 16 x^5 + 10 x^6 + 4 x^7 + x^8\\ (1+x+x^2)^5&=1 + 5 x + 15 x^2 + 30 x^3 + 45 x^4 + 51 x^5 + 45 x^6 + 30 x^7 + 15 x^8 + 5 x^9 + x^{10} \end{align*} Now, note that.

\begin{align*} (1+x+x^2)^n=(1+(x+x^2))^n&=\sum_{k=0}^n \binom{n}{k}(x+x^2)^k=\sum_{k=0}^n \binom{n}{k}x^k(1+x)^k\\ &=\sum_{k=0}^n \binom{n}{k}x^k \sum_{i=0}^k \binom{k}{i}x^i\\ &=\sum_{k=0}^n \sum_{i=0}^k \binom{n}{k}\binom{k}{i}x^{k+i} \end{align*} Using this expresion, we have for $n>3$

\begin{align*} (1+x+x^2)^n&=\sum_{k=0}^n \sum_{i=0}^k \binom{n}{k}\binom{k}{i}x^{k+i}\\ &=\sum_{i=0}^0 \binom{n}{0}\binom{0}{i}x^{0+i}+\sum_{i=0}^1 \binom{n}{1}\binom{1}{i}x^{1+i}+\sum_{i=0}^2 \binom{n}{2}\binom{2}{i}x^{2+i}\\ &+\sum_{i=0}^3 \binom{n}{3}\binom{3}{i}x^{3+i}+\cdots+\sum_{i=0}^n \binom{n}{n}\binom{n}{i}x^{n+i}\\ &=1+\binom{n}{1}\left[\binom{1}{0}x+\binom{1}{1}x^2\right]+\binom{n}{2}\left[\binom{2}{0}x^2+\binom{2}{1}x^3+\binom{2}{2}x^4\right]\\ &+\binom{n}{3}\left[\binom{3}{0}x^3+\binom{3}{1}x^4+\binom{3}{2}x^5+\binom{3}{3}x^6\right]+\cdots+\mbox{other terms}\\ &=1+nx+\left(n+\frac{n(n-1)}2\right)x^2+\left(n(n-1)+\frac{n(n-1)(n-2)}6\right)x^3+\cdots+\mbox{other terms}\\ &=c_0+c_1x+c_2x^2+c_3x^3+\cdots+c_{2n}x^{2n} \end{align*} if $n$ is even is done, but, if $n$ is odd you can proof that $c_2$ or $c_3$ must be even.