DisMat UE 06

ex6-0.pdf

6.1

Find the inverse (polynomial) of $1+x+x^2$

Wir haben

$$P(x)=1+x+x^2$$

nun suchen wir $F(x)$ sodass:

$$P(x)F(x)=1$$

Wir gehen davon aus dass:

$$F(x)=\sum _{n\ge 0}{a}_n{x}^n$$

dazu gilt:
$a_n$ hängt immer nur von $a_n,a_{n-1},a_{n-2},...,a_{n-d}$ mit $d=deg(P(x))$

$$a_n+a_{n-1}+a_{n-2}=0$$ $$a_n=-a_{n-1}-a_{n-2}$$

Nun wenn wir $P(x)$ einsetzen

$$(1+x+x^2)F(x)=1$$

sieht man das

$$a_0=1$$

für $n=1$

$$a_1=-a_0=-1$$

für $n=2$

$$a_2=-a_1-a_0=-(-1)-1=0$$

für $n=3$

$$a_3=-a_2-a_1=-0-(-1)=1$$

für $n=4$

$$a_4=-a_3-a_2=-1-0=-1$$

für $n=5$

$$a_5=-a_4-a_3=-(-1)-1=0$$

… ist

Somit ist

$$\begin{array}{rl}F(x)& =1-x+x^3-x^4+x^6-x^7+...\\ & =\sum _{k\ge 0}{x}^{3k}-x^{3k+1}\\ & =(1-x)\sum _{k\ge 0}{x}^{3k}\\ & =(1-x)\frac{1}{1-x^3}\\ & =\frac{1-x}{1-x^3}\end{array}$$

6.2

Use the method of generating functions for finding an explicit formula for the sequence $\{A_n{\}}_n\ge 0$ given by the recursive data

$$\begin{array}{rl}{A}_0& =A_1=1\\ A_n& =-A_{n-1}-A_{n-2}\text{ for }n\ge 2\end{array}$$ $$G(x)=\sum _{n=0}^{\infty }{A}_n{x}^n$$

Nun wollen wir gucken ob man $G(x)$ vereinfachen kann:

Schreibe die rekursive Formel für $A_n$ als Summe und multipliziere alles mit $x^n$:

$$\sum _{n>2}{A}_n{x}^n=-\sum _{n>2}{A}_{n-1}{x}^n-\sum _{n>2}{A}_{n-2}{x}^n$$

Probiere es als Formel mit $G(x)$ dar zu stellen:

$$\sum _{n>2}{A}_n{x}^n=G(x)-A_0{x}^0-A_1{x}^1=G(x)-A_0-A_{1}x$$ $$\sum _{n>2}{A}_{n-1}{x}^n=x\sum _{m>1}{A}_m{x}^m=x(G(x)-A_0)$$ $$\sum _{n>2}{A}_{n-2}{x}^n=x^2\sum _{m>0}{A}_m{x}^m=x^{2}G(x)$$

⇒

$$\begin{array}{rl}G(x)-A_0-A_{1}x& =-x(G(x)-A_0)-x^{2}G(x)\\ G(x)-1-x& =-x(G(x)-1)-x^{2}G(x)\\ G(x)-1-x& =x-xG(x)-x^{2}G(x)\\ -1-x-x& =-G(x)-xG(x)-x^{2}G(x)\\ 2x+1& =G(x)+xG(x)+x^{2}G(x)\\ & =(1+x+x^2)G(x)\\ G(x)& =\frac{2x+1}{1+x+x^2}\end{array}$$

Wir möchten nun die Gleichung

$$\frac{1}{1-rx}=\sum _{n=0}^{\infty }(rx{)}^n$$

und Partialbruch Zerlegung nutzen um $G(x)$ als Summenformel darzustellen.

$$\begin{array}{rl}G(x)& =\frac{2x+1}{(1-x_{1}x)(1-x_{2}x)}\\ & =\frac{-x_1}{1-x_{1}x}+\frac{-x_2}{1-x_{2}x}\\ & =-x_1\sum _{n=0}^{\infty }(x_{1}x{)}^n+-x_2\sum _{n=0}^{\infty }(x_{2}x{)}^n\end{array}$$

$1+x+x^2=(1-x_{1}x)(1-x_{2}x)$ denn:

$$\begin{array}{rl}{x}_{1,2}& =\frac{-1\pm \sqrt{1-4}}{2}\\ x_1& =\frac{-1+i\sqrt{3}}{2}=e^{2\pi i\frac{1}{3}}\\ x_2& =\frac{-1-i\sqrt{3}}{2}=e^{-2\pi i\frac{1}{3}}\end{array}$$

Dazu fällt auf dass:

$$x_1+x_2=-1x_1{x}_2=1$$

So zeigen wir dass:

$$\begin{array}{rl}& -\frac{x_1}{1-x_{1}x}-\frac{x_2}{1-x_{2}x}\\ & =\frac{-x_1(1-x_{2}x)-x_2(1-x_{1}x)}{(1-x_{1}x)(1-x_{2}x)}\\ & =\frac{-(x_1+x_2)+x(2x_1{x}_2)}{(1-x_{1}x)(1-x_{2}x)}\\ & =\frac{2x+1}{(1-x_{1}x)(1-x_{2}x)}\end{array}$$

und daher:

$$A_n=-x_1^{n+1}-x_2^{n+1}$$

Wenn man $x_1$ und $x_2$ als Trigonometrische Formel darstellt:

$$x_1=e^{2\pi i\frac{1}{3}}{x}_2=e^{-2\pi i\frac{1}{3}}$$

und

$$e^{it}+e^{-it}=2\cos t$$

ist:

$$A_n=-\left(e^{2\pi i(n+1)\frac{1}{3}}+e^{-2\pi i\left(n+1\right)\frac{1}{3}}\right)=-2\cos \left(2\pi \frac{n+1}{3}\right)$$

Dazu gilt:

\begin{array}{ll} 1 & n \equiv 0, 1  & (\text{mod }3) \\ -2 & n \equiv 2 \\ \end{array} \right. $$ denn: Für $n \equiv 0$

A_{n} = -2 \cos \left(\frac{2\pi}{3}\right) = -2 \left(\frac{-1}{2}\right) = 1

Für $n \equiv 1$

A_{n} = -2 \cos \left(\frac{4\pi}{3}\right) = -2 \left(\frac{-1}{2}\right) = 1

Für $n \equiv 2$

A_{n} = -2 \cos (2\pi) = -2

$$????$$