Mathematical induction proof concerning polynomials in Z2.

[VinnyCee]

Homework Statement

For each $$n\,\in\,\mathbb{N}$$, let $$p_n(x)\,\in\,\mathbb{Z}_2[x]$$ be the polynomial

$$1\,+\,x\,+\,\cdots\,x^{n\,-\,1}\,+\,x^n$$

Use mathematical induction to prove that

$$p_n(x)\,\cdot\,p_n(x)\,=\,1\,+\,x^2\,+\,\cdots\,+x^{2n\,-\,2}\,+\,x^{2n}$$

Homework Equations

Induction steps.

$$p_k(x)\,=\,1\,+\,x\,+\,\cdots\,+\,x^{k\,-\,1}\,+\,x^k$$

$$p_{k\,+\,1}(x)\,=\,1\,+\,x\,+\,\cdots\,+\,x^k\,+\,x^{k\,+\,1}$$

The Attempt at a Solution

Is it true for n = 0?

$$p_0(x)\,\cdot\,p_0(x)\,=\,1$$

Yes.Assume that

$$p_k(x)\,\cdot\,p_k(x)\,=\,1\,+\,x^2\,+\,\cdots\,+\,x^{2k\,-\,2}\,+\,x^{2k}$$

is true.

So now I need to show that

$$p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,1\,+\,x^2\,+\,\cdots\,+\,x^{2k}\,+\,x^{2k\,+\,2}$$

is true.
So I start by writing

$$p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,\left(p_k(x)\,+\,x^{k\,+\,1}\right)\,\left(p_k(x)\,+\,x^{k\,+\,1}\right)$$

$$p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,p_k(x)\,p_k(x)\,+\,2\,p_k(x)\,x^{k\,+\,1}\,+\,x^{2k\,+\,2}$$

Assuming that the $$p_k(x)$$ case is true...

$$p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,\left(1\,+\,x^2\,+\,\cdots\,+\,x^{2k\,-\,2}\,+\,x^{2k}\right)\,+\,2\,\left(1\,+\,x\,+\,\cdots\,+\,x^{k\,-\,1}\,+\,x^k\right)\,x^{k\,+\,1}\,+\,x^{2k\,+\,2}$$

$$p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,\left(1\,+\,x^2\,+\,\cdots\,+\,x^{2k\,-\,2}\,+\,x^{2k}\right)\,+\overbrace{\,2\,\left(x^{k\,+\,1}\,+\,x^{k\,+\,2}\,+\,\cdots\,+\,x^{2k}\,+\,x^{2k\,+\,1}\right)}^{0}\,+\,x^{2k\,+\,2}$$But now what do I do??Thanks to Sethric!

Since we are working in $$\mathbb{Z}_2$$, the middle term is zero $$\left(0\,\equiv\,2\,(mod\,2)\right)$$ and the expression becomes

$$p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,\left(1\,+\,x^2\,+\,\cdots\,+\,x^{2k\,-\,2}\,+\,x^{2k}\right)\,+\,x^{2k\,+\,2}$$

$$\therefore\,\,\,p_{k\,+\,1}(x)\,\cdot\,p_{k\,+\,1}(x)\,=\,1\,+\,x^2\,+\,\cdots\,+\,x^{2k}\,+\,x^{2k\,+\,2}\,\,\,\blacklozenge$$

 

[Sethric]

What does that coefficient of 2 do when you are dealing with Z_2?

 

[VinnyCee]

Thanks so much! I thought that $$p_n(x)\,\in\,\mathbb{Z}_2$$ would come into play somehow; it was right in front of me!