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!