0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ For $n=1$ all of the coefficients are $1$, and thus none is even. $\endgroup$ – Mark Viola Sep 13 '15 at 20:14
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.